Компонента связности графа

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Несвязный граф с тремя компонентами связности

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Для ориентированных графов определено понятие сильной компоненты связности

Алгоритм[править | править исходный текст]

Для поиска компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным (относительно количества вершин и ребер).

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Видеозапись лекции посвященной связности графов