4 Алгоритм Габова

4.1 Описание алгоритма

В1999 году Г. Габову удалось получить эффективный алгоритм поиска сильной связности.

Валгоритме Габова вершины заносятся в главный стек — но параллельно заносятся во второй стек вершины, лежащие на пути поиска, о которых известно, что они находятся в других сильных компонентах, и выталкиваются все вершины после достижения каждого обратного ребра. Когда завершается обработка вершины v (v находится на верхушке второго стека — на рисунке заштриховано), ясно, что все вершины, расположенные над v в главном стеке, находятся в одном и том же сильном компоненте. [8]

4.2 Реализация

Данная альтернативная реализация рекурсивной функции-члена использует вместо вектора 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)

11if (path.top() == w) path.pop(); else return;

12do { id[v = S.pop()] = scnt; } while (v != w);

13scnt++;

14}

13