Нахождение компонент связанности графа (Пояснительная записка к курсовой работе), страница 2

Непосредственно из определения компоненты связанности графа следует два возможных алгоритма решения задачи. Первый вариант следует из транзитивности отношения связанности и рефлексивности неориентированного графа: найти рефлексивно-транзитивное замыкание графа, и выбрать неповторяющиеся строки. Анализ сложности при табличной реализации показывает время O(N³) и объем памяти O(N²).

Второй вариант — это зафиксировать произвольную вершину x_i, перебрать все вершины (x_j | i ¹ j) и проверить существует ли путь между x_i и x_j. Все вершины x_j, для которых выполняется это утверждение, составляют компоненту связанности. Предварительный анализ сложности показывает время O((N-1)N²) [перебор вершин дает O(N(N-1)) и выполнение проверки пути имеет сложность O(N)], объем памяти O(N).

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

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

1.  Раскрасить все вершины графа в красный цвет

2.  Если есть вершины красного цвета, выполнить следующий шаг, иначе закончить выполнение алгоритма.

3.  Выбрать одну произвольную вершину x_i красного цвета и покрасить ее в ультрафиолетовый цвет. Эта вершина, очевидно, принадлежит своей компоненте связанности, но ее окружение еще не рассмотрено.

4.  Повторять следующий шаг, пока есть хоть одна вершина ультрафиолетового цвета. Если таких вершин нет, перейти к шагу 2. Все вершины, покрашенные в синий цвет на данной итерации шага 3 принадлежат одной компоненте связанности.

5.  Выбрать вершину ультрафиолетового цвета и покрасить ее в синий цвет, а все красные вершины, смежные с ней, в ультрафиолетовый.

Этот алгоритм классифицирован как волновой — из случайно выбранной точки разгоняем круговую волну, помечая все точки, попавшие на волновой фронт, как одну компоненту связанности.

Так, как алгоритм рассматривает каждую точку только один раз, и использует минимально необходимое количество смежных вершин, то сложность приведенного алгоритма O(N), требуемая память O(N).

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

Применяя стратегию деления пополам, получим следующий, четвертый алгоритм:

пусть X —вершины, рассматриваемые на каждом шаге, тогда

1.  если |X| = 1, вернуть {X}

2.  иначе разделить X на два подмножества A и B и вызвать алгоритм рекурсивно.

3.  пусть {Z} – множества вершин, полученные после применения последнего шага, тогда для всех пар (z_i, z_j| i ¹ j), проверить связанность множеств Z_i, Z_j, объединяя их, если хоть одна вершина из Z_i смежна c Z_j. Вернуть результат объединений.

Общее количество сливающих проверок C(N,2), следовательно, временная сложность алгоритма  , что заведомо хуже, чем у волнового алгоритма.

Выбор алгоритма и структур данных

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

Этот алгоритм требует хранения множества вершин, с операциями выборки любого элемента, проверки принадлежности и быстрым удалением (красное множество). Неплохим выбором для этого множества будет хеш-таблица, имеющая временные затраты O(1) для последних двух операций. Операция выборки любого элемента из хеш-таблицы может быть реализована при помощи двухсвязанных списков, объединяющих все элементы множества. Автор принял решение[1] не создавать собственную реализацию хеш-таблиц со связанными элементами, а использовать готовую, поставляемую с языком XLisp.