Алгоритм Фараджева

Алгоритм Фараджева — основанный основанный на поиске в глубину алгоритм отыскания бикомпонент в орграфе, предложенный И.А. Фараджевым в 1970 г.

В основе алгоритма лежит следующая идея. Как только в процессе поиска в глубину в графе будет обнаружен контур, он немедленно стягивается в одну составную вершину. Кроме того, если из вершины нет возможности продвинуться в глубь графа, то возвращение из нее сопровождается ее удалением из графа. Удаленные вершины заносятся в список бикомпонент; составные вершины в нем определяют нетривиальные бикомпоненты. Легко увидеть, что незначительная модификация алгоритма превращает его в алгоритм построения графа Герца.

Трудоемкость алгоритма [math]\displaystyle{ O(m + n \log n) }[/math] для орграфа с [math]\displaystyle{ \,n }[/math] вершинами и [math]\displaystyle{ \,m }[/math] дугами.

Литература

• Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.