В 1972 году был предложен алгоритм Тарьяна поиска компонент сильной связности.
Алгоритм Тарьяна можно понимать как вариацию алгоритма поиска в глубину, в котором при посещении вершины и окончании обработки вершины выполняются дополнительные действия. Посещение вершины происходит при движении от корня к листьям, а окончание обработки вершины — на обратном пути. При посещении вершины она проталкивается во вспомогательный стек, а выталкивается при окончании обработки.
Индексы компонент связности всех вершин хранятся в векторе id, индексированном номерами вершин. Вектор low отслеживает вершину с наименьшим номером в прямом порядке обхода, достижимую из каждого узла через последовательность прямых связей, за которыми следует одна восходящая связь. Воспользовавшись поиском в глубину с тем, чтобы рассматривать вершины в обратном топологическом порядке, мы вычисляем для каждой вершины v максимальную точку, достижимую через обратную связь из предшественника (low[v]). Когда для вершины v выполняется pre[v] = low[v], мы выталкиваем её из стека, а также все вершины выше её и всем им присваиваем номер следующей компонент [7]
Алгоритм Тарьяна похож на алгоритм поиска мостов в неориентированных графах. Этот метод основан на двух наблюдениях, которые были сделаны в других контекстах. Во-первых, мы рассматриваем вершины в обратном топологическом порядке, чтобы в конце работы рекурсивной функции для вершины мы знали, что не встретим ни одной вершины из того же сильного компонента (потому что все вершины, достижимые из этой, уже обработаны). Во-вторых, обратные ссылки в дереве обеспечивают второй путь из одной вершины в другую и связывают сильные компоненты.
Алгоритм имеет временную сложность O(V + E)O(V + E), где E E —
количество рёбер, а V V — вершин графа
1 #include "STACK.cc"
2template <class Graph>
3 class SC
11
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
{const Graph &G;
STACK<int> S;
int cnt, scnt;
vector<int> pre, low, id;
void scR(int w)
{int t;
int min = low[w] = pre[w] = cnt+ + ;
S.push(w);
typename Graph::adjIterator A(G, w);
for (t = A.beg(); !A.end(); t = A.nxt())
{if (pre[t] == -1) scR(t);
if (low[t] < min) min = low[t];
}
if (min < low[w]) { low[w] = min; return; }
do
{ id[t = S.pop()] = scnt; low[t] = G.V(); }
while ( t ! = w) ;
scnt++;
}
public:
SC(const Graph &G) : G(G), cnt(0), scnt(0),
pre(G.V(), -1), low(G.V()), id(G.V())
{ for (int v = 0; v < G.V(); v++)
if (pre[v] == -1) scR(v);
}
int count() const { return scnt; }
bool stronglyreachable(int v, int w) const
{ return id[v] == id[w]; }
};
12
В1999 году Г. Габову удалось получить эффективный алгоритм поиска сильной связности.
Валгоритме Габова вершины заносятся в главный стек — но параллельно заносятся во второй стек вершины, лежащие на пути поиска, о которых известно, что они находятся в других сильных компонентах, и выталкиваются все вершины после достижения каждого обратного ребра. Когда завершается обработка вершины v (v находится на верхушке второго стека — на рисунке заштриховано), ясно, что все вершины, расположенные над v в главном стеке, находятся в одном и том же сильном компоненте. [8]
Данная альтернативная реализация рекурсивной функции-члена использует вместо вектора low, индексированного номерами вершин, второй стек path, чтобы определять, когда нужно выталкивать из главного стека вершины каждого сильного компонента
1 void scR(int w)
2{ int v;
3pre[w] = cnt++;
4S.push(w); path.push(w);
5typename Graph::adjIterator A(G, w);
6for (int t = A.beg(); !A.end(); t = A.nxt())
7if (pre[t] == -1)
8 scR(t);
9else if (id[t] == -1)
10 |
while (pre[path.top()] > pre[t]) path.pop(); |
11if (path.top() == w) path.pop(); else return;
12do { id[v = S.pop()] = scnt; } while (v != w);
13scnt++;
14}
13
Все рассмотренные в данном разделе алгоритмы поиска компонент сильной связности имеет огромное значение для решения других задач. Было рассмотрено три алгоритма. С практической точки зрения время выполнения всех этих алгоритмов пропорционально количеству ребер орграфа, и различия в производительности больше зависят от деталей реализации. Например, внутренний цикл алгоритмов Тарьяна и Габова составляют операции АТД стека магазинного типа. Реализация алгоритма Косарайю — пожалуй, простейшая из всех трех, но она содержит небольшой недостаток (для разреженных графов): в ней выполняются три прохода по ребрам (один проход для построения обратного графа и два прохода поиска в глубину).
14
1Сильная связность [электронный ресурс]. — URL: https://scask.ru/e_ book_cla.php?id=46 (Дата обращения 06.12.2020).
2Поиск компонент сильной связности: алгоритм косарайю [электронный ресурс]. — URL: https://habr.com/ru/post/331904/ (Дата обращения 06.12.2020).
3 Глава |
28. |
связность |
в |
орграфах |
[Электронный |
ресурс]. — |
URL: |
http://matica.org.ua/metodichki-i-knigi-po-matematike/ |
|||||
diskretnaia-matematika-uchebnoe-posobie/ glava-28-sviaznost-v-orgrafakh (Дата обращения 07.12.2020).
4 Поиск компонент сильной связности, построение конденсации графа [электронный ресурс]. — URL: https://e-maxx.ru/algo/strong_ connected_components (Дата обращения 06.12.2020).
5Лекция 13. графы [электронный ресурс]. — URL: http://vuz.exponenta. ru/pdf/L13.html (Дата обращения 06.12.2020).
6 Сильно связные графы и компоненты графа [электронный |
ресурс]. — |
URL: https://scask.ru/j_book_graph.php?id=9 (Дата |
обращения |
06.12.2020). |
|
7 Понятие сильной связности. анализ сильной связности с помощью алгоритмов поиска на графах. [электронный ресурс]. — URL: https:// infopedia.su/9x117a1.html (Дата обращения 07.12.2020).
8Сильные компоненты в орграфах [электронный ресурс]. — URL: https:// intuit.ru/studies/courses/12181/1174/lecture/25266?page=11 (Дата обращения 07.12.2020).
15