Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 19. Орграфы и ориентированные ациклические графы. Чтобы вычислить сильные компоненты орграфа, изображенного внизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева)
|
|
РИСУНОК 19.28. ВЫЧИСЛЕНИЕ СИЛЬНЫХ КОМПОНЕНТ (АЛГОРИТМ КОСАРАЙЮ)
Чтобы вычислить сильные компоненты орграфа, изображенного внизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратного порядка обхода, который присваивает вершинам индексы в порядке, в каком завершаются рекурсивные DFS (сверху). Этот порядок эквивалентен обратному порядку обхода леса DFS (вверху справа). Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (внизу). Сначала мы проверяем все узлы, доступные из вершины 9, затем осуществляем просмотр этого вектора справа налево, обнаруживая при этом, что 1 есть крайняя справа непосещенная вершина, поэтому мы выполняем рекурсивный вызов для вершины 1 и т.д. Деревья в лесе DFS, которые выбираются в результате этого процесса, представляют собой сильные компоненты: все вершины каждого дерева имеют те же значения, что и вектор id, индексированный именами вершин (внизу).
Часть 5. Алгоритмы на графах
template < class Graph> class SC { const Graph & G; int cnt, sent;
vector< int> postl, postR, id; void dfsR (const Graph & G, int w) {
id[w] e scnt;
typename Graph:: adjIterator A(G, w); for (int t = A.beg();! A.end(); t = A.nxt())
if (id[t] == -1) dfsR(G, t); postI[cnt++] = w; } public:
SC (const Graph & G): G(G), cnt(O), scnt(O), postI(G.VO), postR(G.V()), id(G.V()/ -1) { Graph R(G.V(), true); reverse (G, R); for (int v = 0; v < R.V(); v++)
if (id[v] == -1) dfsR(R, v); postR = postI; cnt = sent = 0; id.assign(G.V(), -1);
for (int v = G.V()-1; v > = 0; v—) if (id[postR[v]] == -1)
{ dfsR(G, postR[v]); scnt++; } }
int count() const { return scnt; } bool stronglyreachable (int v, int w) const { return id[v] == id[w]; }
};
Свойство 19.14. Метод Косарайю обеспечивает обнаружение сильных компонент графа ценой линейных затрат времени и пространства памяти.
Доказательство: Этот метод состоит из двух процедур поиска в глубину, подвергнутых незначительным изменениям, благодаря чему время его выполнения, как обычно, пропорционально V2 в случае насыщенных графов и V + Ев случае разреженных графов (если графы представлены в виде списков смежных вершин). Чтобы проверить, что он правильно вычисляет сильные компоненты, мы должны доказать на втором просмотре, что две вершины s и t содержатся в одном и том же дереве леса DFS тогда и только тогда, когда они взаимно достижимы.
Если вершины s u t взаимно достижимы, они обязательно будут находиться в одном и том же дереве DFS, поскольку, когда просматривается первая из них, вторая остается непосещенной и достижимой из первой и непременно будет просмотрена, прежде чем завершится рекурсивный вызов из корня.
Чтобы доказать противное, предположим, что s и t включены в одно и то же дерево, и пусть rесть корень этого дерева. Из того факта, что s достижима из r (через ориентированный путь, состоящий из ребер дерева), следует, что существует ориентированный путь из s в r в обратном орграфе. Теперь остается доказать, что должен существовать путь из rв s в обратном орграфе, поскольку rимеет более высокий номер в обратном порядке обхода, чем s (из-за того, что при втором поиске в глубину rбыла выбрана первой в то время, когда обе вершины еще не посещались), и существует путь из s в r. Если бы пути из s в r не было, то путь из s в rв обратном орграфе остав-