Знаходження компонент сильної зв'язності орієнтованого графа

Компонентою сильної зв'язності орієнтованого графа називається максимальна множина його вершин, в якій існують шляхи з будь-якої вершини в будь-яку іншу. Так наприклад, граф , зображений на рисунку що міститься нижче, складається з чотирьох компонент сильної зв'язності: , , і .

komponenty_sylnoi_zvjaznosti_grafa110

Орієнтований граф та його компоненти сильної зв'язності

Як видно з рисунка, кожна вершина орієнтованого графа  належить певній компоненті сильної зв'язності, але деякі ребра можуть не належати жодній з них. Такі ребра з'єднують вершини з різних компонент.

Читати повністю