3 Алгоритм Тарьна
3.1 Описание алгоритма
В 1972 году был предложен алгоритм Тарьяна поиска компонент сильной связности.
Алгоритм Тарьяна можно понимать как вариацию алгоритма поиска в глубину, в котором при посещении вершины и окончании обработки вершины выполняются дополнительные действия. Посещение вершины происходит при движении от корня к листьям, а окончание обработки вершины — на обратном пути. При посещении вершины она проталкивается во вспомогательный стек, а выталкивается при окончании обработки.
Индексы компонент связности всех вершин хранятся в векторе id, индексированном номерами вершин. Вектор low отслеживает вершину с наименьшим номером в прямом порядке обхода, достижимую из каждого узла через последовательность прямых связей, за которыми следует одна восходящая связь. Воспользовавшись поиском в глубину с тем, чтобы рассматривать вершины в обратном топологическом порядке, мы вычисляем для каждой вершины v максимальную точку, достижимую через обратную связь из предшественника (low[v]). Когда для вершины v выполняется pre[v] = low[v], мы выталкиваем её из стека, а также все вершины выше её и всем им присваиваем номер следующей компонент [7]
Алгоритм Тарьяна похож на алгоритм поиска мостов в неориентированных графах. Этот метод основан на двух наблюдениях, которые были сделаны в других контекстах. Во-первых, мы рассматриваем вершины в обратном топологическом порядке, чтобы в конце работы рекурсивной функции для вершины мы знали, что не встретим ни одной вершины из того же сильного компонента (потому что все вершины, достижимые из этой, уже обработаны). Во-вторых, обратные ссылки в дереве обеспечивают второй путь из одной вершины в другую и связывают сильные компоненты.
Алгоритм имеет временную сложность O(V + E)O(V + E), где E E —
количество рёбер, а V V — вершин графа
3.2 Реализация
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