В этом уроке разберем, что такое взвешенный граф и для чего он полезен. Также познакомимся с алгоритмом Крускала, и рассмотрим, как и почему он работает.
Что такое взвешенный граф
Взвешенный граф — это граф, в котором каждое ребро обозначается числом. Это число — его вес:
Вес — это стоимость использования данного ребра. Например, приведенный выше граф может представлять дорожную сеть, где вершины — это города, ребра — дороги между ними, а вес — стоимость строительства этих дорог.
Предположим, что мы хотим построить дороги, чтобы добраться из одного города в другой. Нам нужно сделать это как можно дешевле. Так может выглядеть ответ:
В этом случае нам не нужны циклы, так как мы пытаемся сделать все как можно дешевле. Мы хотим добираться до любой вершины графа, поэтому нам нужно минимальное охватывающее дерево, в котором сумма весов всех ребер в дереве как можно меньше.
Существует несколько алгоритмов, чтобы найти минимальные прямые деревья. В этом уроке мы рассмотрим алгоритм Крускала.
Что такое алгоритм Крускала
Алгоритм Крускала строит охватывающее дерево графа $G$ по одному ребру за раз. На каждом шаге алгоритма мы берем ребро $G$ с таким весом, чтобы добавление этого ребра в строящееся дерево не создавало цикла.
Мы можем разрывать связи между весом ребер как угодно, или добавлять ребра до тех пор, пока это не станет невозможным. В графе с $n$ вершинами нам всегда потребуется добавить ровно $n - 1$ ребро.
Так это выглядит (грани выделены в порядке их добавления):
С помощью алгоритма Крускала на каждом шаге выбирается самое дешевое доступное ребро. В этом случае не нужно задумываться о будущих последствиях этого выбора. Эта стратегия всегда дает минимальное остовное дерево.
Почему алгоритм Крускала работает
Разберем несколько причин, почему граф $T$, который строит алгоритм Крускала, действительно остовное дерево графа:
- У $T$ нет циклов, поскольку алгоритм Крускала не может их создать
- $T$ — связной граф, иначе мы могли бы добавить ребро между компонентами $T$ без цикла
- $T$ — охватывающий граф, который включает каждую вершину. Иначе мы могли бы добавить ребро из $T$ в вершину, которая не входит в $T$, не вызывая цикла
- Мы знаем, что у деревьев на $n$ вершинах всегда $n-1$ ребро, поэтому нам нужно добавить ровно $n - 1$ ребро
Теперь рассмотрим, почему у дерева Крускала $T$ — минимальный вес. Представим минимальное расходящееся дерево $S$, которое не равно $T$. Когда мы проходим через процесс Крускала и добавляем ребра, мы добавляем в $T$ ребро $e$, которое не является частью $S$.
Предположим, мы попытаемся добавить $e$ в $S$. Это создаст цикл по основным свойствам деревьев. Вдоль этого цикла должно быть еще какое-то ребро $d$, которого нет в $T$. $T$ — это дерево, и оно не может содержать все ребра этого цикла.
В этом примере показана гипотетическая часть $S$ вместе с $d$ и $e$:
Теперь удалим $d$ из $S$ и заменим его на $e$ — это дерево $S - d + e$. Если просто менять одно ребро цикла на другое, $S - d + e$ все равно прямое дерево $G$.
Процесс Крускала добавил ребро $e$, а не $d$. Это означает, что вес $e$ меньше или равен весу $d$. Это делает $S - d + e$ минимальным прямым деревом $G$, которое согласуется с $T$ на одно ребро больше, чем $S$.
Мы можем повторять этот процесс, пока не получим минимальное остовное дерево, которое согласуется с $T$ по каждому ребру. Это означает, что $T$ должно быть минимальным остовным деревом.
Выводы
Мы разобрались, что такое взвешенный граф и для чего он полезен. Также познакомились с алгоритмом Крускала, и поняли, почему он работает. Написать код, который реализует алгоритм Крускала, несложно. Самое сложное — проверить, не создает ли добавление ребра цикл. Например, это можно сделать с помощью структуры данных disjoint set.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
