Алгоритм поиска компонент связности в графе

ВВЕДЕНИЕ
Структуры данных являются фундаментальной концепцией в области информатики и программирования [1]. Они представляют собой способы организации и хранения данных, которые позволяют эффективно решать различные вычислительные задачи. Выбор подходящей структуры данных имеет критическое значение для разработки высокопроизводительных и масштабируемых программных систем.
Целью данной курсовой работы является исследование и реализация ключевых структур данных, а также анализ их свойств, эффективности и областей применения.
Структура курсовой работы включает в себя следующие основные разделы:
Обзор теоретических основ задач, связанных с структурами данных. В этом разделе будут рассмотрены базовые концепции, классификация и общие принципы реализации различных структур данных.
Описание входной и выходной информации в сформулированных задачах.
Описание алгоритмов решения задач, сводящихся к применению структур данных.
Программная реализация задач на использование структур данных.
Описание требований к функциональности и основных результатов.



1 ЗАДАЧА 1
1.1 Постановка задачи
Графом (G, X) называется совокупность двух конечных множеств: множества точек, которые называются вершинами (X = {Х1,...,Хn}), и множества связей в парах вершин, которые называются дугами, или ребрами в зависимости от наличия или отсутствия направленности связи.
Ребром называются две встречные дуги (Хi, Хj) и (Хj, Хi). На графе они изображаются одной линией без стрелки. Ребро, или дуга, концевые вершины которого совпадают, называется петлей [1-5].
Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.
Две вершины, являющиеся концевыми для некоторого ребра или некоторой дуги, называются смежными. Соответственно этот граф может быть представлен матрицей смежности либо матрицей инцидентности.
Понятие компоненты связности вытекает из понятия связности графа. Попросту говоря, компонента связности - часть графа (подграф), являющаяся связной. Формально, компонента связности - набор вершин графа, между любой парой которых существует путь.
Поиск компонент связности может быть связан с поиском в глубину или поиском в ширину на графе.
Одним из методов поиска в орграфе является поиск в глубину. Порядок “посещения” вершин при поиске в глубину определяется следующими правилами [2]:
1. Посещаем начальную вершину vi и считаем её текущей.
2. Если vt – текущая вершина, vj – вершина, смежная вершине vt и ещё не посещалась, то посещаем её и считаем текущей.
3. Если исходная вершина vi – текущая вершина и все смежные с ней уже посещались, то поиск заканчивается.
4. Если vt – текущая вершина и все смежные с ней уже посещались, то текущей считаем вершину, из которой пришли в вершину vt.
Процесс поиска в глубину можно представить как построение ориентированного дерева, корнем которого является начальная вершина орграфа, остальные вершины дерева – вершины орграфа, достижимые из начальной. Дуги дерева соответствуют дугам орграфа, по которым осуществлялось “движение” во время поиска [3,4].
Рассмотрим следующий пример. Пусть дан граф следующей структуры

Рис. 1.1. Структура графа для обхода в глубину
Будем хранить в массиве Visited посещенные вершины. В массиве Stack будем хранить вершины, смежные с текущей. Ситуация с выбором начальной вершины 0 показана на рисунке 1.2.

Рис. 1.2. Выбор начальной вершины для обхода в глубину
Вершина 0 будет помечена как посещенная. Из вершины стека выберем вершину 1 и перейдем к ней (рисунок 1.3).

Рис. 1.3. Переход к вершине 1 при обходе в глубину
Ближайшей вершиной для последующего перехода является вершина 2. Выберем ее для обхода (рисунок 1.4).

Рис. 1.4. Переход к вершине 2 при обходе в глубину
В данном случае соседней вершиной с вершиной 2 является вершина 4. Добавим ее в стек. Переход к вершине 4 показан на рисунке 1.5.

Рис. 1.5. Переход к вершине 4 при обходе в глубину
Следующей за вершиной 4 и единственной вершиной, остающейся в стеке, является вершина 3. Переход к вершине 3 показан на рисунке 1.6.

Рис. 1.6. Переход к вершине 3 при поиске в глубину
Данная вершина уже не имеет непосещенных соседей, так что ее посещение будет финальной стадией алгоритма.
Для программной реализации метода поиска в глубину можно использовать рекурсивный или итеративный алгоритм. В алгоритмах используется множество V’ вершин, достижимых из начальной. В исходном состоянии оно содержит только начальную вершину. В итеративном алгоритме для запоминания вершин, предшествующих текущей, используется стек. Дерево поиска можно сохранить в массиве T, количество элементов которого равно количеству вершин орграфа. Элемент Ti представляет собой вершину, предшествующую вершине i в дереве.
Поиск в ширину или BFS (breadth-first search, поиск "сначала в ширину") - это метод обхода графа, по которому после стартовой вершины сначала отмечаются все вершины смежные с ней, то есть все достижимые за один шаг, а потом все достижимые за два (смежные с предыдущими и не смежные со стартовой), а потом за три шага и т.д. Это напоминает распространение волны, поэтому поиск в ширину называет методом волны.
Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий:
1.Посещенные.
2.Не посещенные.
Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов.
Алгоритм работает следующим образом:
1.Начните с размещения любой вершины графа в конце очереди.
2.Возьмите передний элемент очереди и добавьте его в список посещенных.
3.Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в конец очереди.
4.Продолжайте повторять шаги 2 и 3, пока очередь не опустеет.
Граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм BFS на каждом узле.
Рассмотрим применение алгоритма BFS на следующем примере (рисунок 1.7)

Рис. 1.7. Начальная конфигурация графа
Массив посещенных вершин обозначим как Visited, а очередь, в которой будут пребывать вершины, как Queue. Начнем обход графа в ширину с посещения вершины 0. Результаты посещения вершины 0 представлены на рисунке 1.8.