C3D Toolkit  Kernel - 105122, Vision - 0.181114.105122
Шаблон класса MtStrongComponents< Graph, SCVisitor, VertexPropertyMap >

Алгоритм поиска компонент сильной связности в орграфе Подробнее...

Открытые члены

void operator() ()
 Исполнить алгоритм поиска сильных компонентов
 

Подробное описание

template<class Graph, class SCVisitor, class VertexPropertyMap>
class MtStrongComponents< Graph, SCVisitor, VertexPropertyMap >

Алгоритм поиска компонент сильной связности в орграфе

Напомним, что две вершины орграфа считаются сильно связанными, если существует маршрут из первой вершины ко второй и обратный маршрут из второй к первой. Подграф называется сильно связным, если любая пары его вершин сильно связаны. Компонент сильной связности графа - это один из его сильно сзязный подграфов G', для которого не существует сильно связной пары вершин u и v, таких, что u-принадлежит G', а v не принадлежит G'. Другими словами, вершины компонента сильной связости принадлежат классу взаимной достижимости вершин;

Заметки
Алгоритм MtStrongComponents имеет линейную сложность вычислений

Объявления и описания членов класса находятся в файле: