Поиск компонент связности

 

Формулировка задачи

 

Дан произвольный граф возможно состоящий из нескольких компонент связности. И дана произвольная вершина графа. Требуется выделить компоненту связности содержащую данную вершину.

 

Идея алгоритма

 

Предположим, что про некоторое количество вершин уже известно, что они принадлежат искомой компоненте связности. Присвоим этим вершинам некоторое число, будем называть его статусом и договоримся, что для вершин принадлежащих компоненте этот статус имеет вполне определённое значение. Тогда расширить множество вершин принадлежащих компоненте можно простой процедурой:

§         Возьмём любую вершину чей статус говорит о том, что вершина принадлежит компоненте связности.

§         Передадим её статус всем вершинам соединенным с ней ребром.

 

 

Алгоритм

 

§         Присвоим всем вершинам статус 1.

§         Присвоим ИСХОДНОЙ вершине статус 2.

§         Пока есть вершины имеющие статус = 2 выполнить

o       Выберем любую вершину имеющую статус 2 назовем её ТЕКУЩЕЙ

o       Для всех вершин инцидентных ТЕКУЩЕЙ выполнить

§         Если вершина имеет статус 1 то её статус = 2

o       Статус ТЕКУЩЕЙ вершины = 3

 

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