Набор всех компонент связности

До настоящего момента мы говорили о компоненте связности, содержащей конкретный узел s. Однако для каждого узла в графе существует своя компонента связности. Какими отношениями связаны эти компоненты?

Как выясняется, эти отношения четко структурированы и описываются следующим утверждением.

(3.8) Для любых двух узлов s и t в графе их компоненты связности либо идентичны, либо не пересекаются.

Это утверждение интуитивно понятно, если взглянуть на граф наподобие изображенного на рис. 3.2. Граф разделен на несколько частей, не соединенных ребрами; самая большая часть — компонента связности узлов 1–8, средняя — компонента связности узлов 11, 12 и 13 и меньшая — компонента связности узлов 9 и 10. Чтобы доказать это общее утверждение, достаточно показать, как точно определяются эти «части» для произвольного графа.

Доказательство. Возьмем любые два узла s и t в графе G, между которыми существует путь. Утверждается, что компоненты связности, содержащие s и t, представляют собой одно и то же множество.

Действительно, для любого узла v в компоненте s узел v также должен быть достижим из t через путь: мы можем просто перейти из t в s, а затем из s в v. Аналогичные рассуждения работают при смене ролей s и t, так что узел входит в компоненту одного в том, и только том случае, если он также входит в компоненту другого.

С другой стороны, если пути между s и t не существует, не может быть узла v, входящего в компоненту связности каждого из них. Если бы такой узел v существовал, то мы могли бы перейти от s к v, а затем к t, строя путь между s и t. Следовательно, если пути между s и t не существует, то их компоненты связности изолированы.

Из этого доказательства вытекает естественный алгоритм получения всех компонент связности графа, основанный на расширении одной компоненты за раз. Алгоритм начинает с произвольного узла s, а затем использует BFS (или DFS) для генерирования его компоненты связности.

Далее мы находим узел v (если он существует), который не был посещен при поиске от s, и итеративным методом, используя BFS от узла v, генерирует компоненту связности — которая, согласно (3.8), изолирована от компоненты s. Это продолжается до тех пор, пока алгоритм не посетит все узлы.