Часть 5. Алгоритмы на графах. конкретной задачи, то алгоритмы объединения-поиска, которые мы рассматривали в главе 1, самые быстрые

конкретной задачи, то алгоритмы объединения-поиска, которые мы рассматривали в главе 1, самые быстрые, поскольку они выполняют построение структуры данных, предназначенной специально для решения данной задачи, а поэтому не нуждаются в другом представлении графа. Но если структура данных, представляющая граф, уже построена, то алгоритмы DFS и BFS демонстрируют более высокое быстродействие и большую гибкость. Добавление проверки с целью прекращения выполнения алгоритма, когда известно, что граф представляет собой единую связную компоненту, существенно повышает быстродействие поиска в глубину и алгоритма объединения-поиска (но не поиска в ширину) при обработке насыщенных графов.

Обозначения

U - взвешенное быстрое объединение посредством сжатия пути делением пополам (программа 1.4)

I - начальная конструкция представления графа

D - рекурсивный поиск в глубину

В - поиск в ширину (программа 18.9)

* - выход, когда установлен факт полной связности графа

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

Во-первых, из таблицы ясно, что не следует использовать представление графа в виде матрицы смежности в случае разреженных графов больших размеров (и нельзя его ис­пользовать применительно к очень большим графам), причем не только в силу того, что затраты на инициализацию матрицу неприемлемы, но и по причине того, что алгоритм