6.6. Выделение компонент связности

Рассмотрим алгоритм нахождения числа компонент связности, а также выделения этих компонент на неориентированном графе. Подобным образом решается задача и для ориентированного графа. В основу рассматриваемого алгоритма 6.3 выделения компонент связности положена описанная ранее техника поиска в глубину на графе Структура алгоритма 6.3 является модификацией в сторону упрощения основного алгоритма 6.1 поиска в глубину. Работа алгоритма 6.3 направлена на формирование вектора меток вершин графа. Элементу присваивается общий номер той компоненты, которой принадлежит вершина Сложность алгоритма 6.3, как и алгоритма 6.1, составляет

Алгоритм 6.3. Выделение связных компонент неориентированного графа

(см. скан)

(см. скан)

Программная реализация выделения компонент связности представлена в алгоритме 6.4, который близко соотносится с соответствующим множественным описанием алгоритма 6.3. Рассмотрим пример расчета по программе алгоритма 6.4 выделения компонент связности графа, представленного на рис. 6.14.

Рис. 6.14. Пример выделения компонент связности графа

Для программы алгоритма 6.4 исходные данные структуры смежности графа на рис. 6.14 задаются в текстовом файле Connect.in. Структура (правило) заполнения файла одинакова с той, которая описана в рассмотренном примере поиска в глубину при расчете по программе алгоритма 6.2.

Данные файла Connect.in для примера на рис. 6.14:

Результаты расчетов сохраняются в выходном файле Connect.out со следующей структурой:

Алгоритм 6.4. Программа выделения связных компонент неориентированного графа

(см. скан)

(см. скан)

(см. скан)