Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня20 тем по алгоритмам и структурам данныхВ статье мы продолжаем работу с алгоритмом минимального остовного дерева, чтобы закончить его.
В прошлой статье мы в основном изучили алгоритм Крускала для минимального остовного дерева. Сегодня давайте узнаем об алгоритме Прима, чтобы понять эту проблему с другой точки зрения.
от края до края
Кратко рассмотрим принцип работы алгоритма Крускала.Хотя в предыдущей статье было использовано много места, принцип очень прост. По сути, у нас есть все ребра в графеСортировать по длине, а затем добавляем его в дерево как основу дерева по порядку.
В этом процессе, чтобы избежать генерации циклов и разрушения древовидной структуры, мы используем алгоритм поиска объединения для обслуживания. Учитываться будут только те ребра, которые не входят в связный блок, иначе образуется цикл.
Изучив этот алгоритм, многие поймут его какЖадная проблема, или сценарий использования поиска объединения. Это верно, но есть лучшее объяснение этой проблемы.
Это объяснениерасширение набора ребер.
Весь процесс операции Крускала заключается в том, что мы непрерывно выбираем ребра для соединения с деревом.Для графа с n точками нам нужно n-1 ребер. Если ориентироваться на этот набор выбранных ребер, то при запуске алгоритма он пуст, а после окончания прогона содержит n-1 ребер и достигает насыщения.
Конечно, на это можно посмотреть и под другим углом: если мы сосредоточимся на сути, то процесс построения минимального остовного дерева также можно рассматривать какрасширение набора точек. Просто точка отличается от ребра.Ребро можно выбрать, а точку нельзя.Точку можно накрыть только выбрав ребро. Например, давайте посмотрим на следующий рисунок:
На рисунке слева у нас построено дерево, соединяя AE, мы накрываем ребром точку E. Точка основана на ребре, и точку нельзя покрыть, не пройдя через ребро.
Начнем с пустого множества, за исключением того, что первое ребро может покрывать две точки, а каждое последующее ребро соединяет точку, которая была покрыта, и точку, которая не покрыта. Тогда также возможно покрыть n точек через n-1 ребер. Это основная идея алгоритма Прима, который является расширением набора точек.
вся идея
Мы понимаем, что основная идея Prim заключается в том, что расширение набора точек легко, потому что стороны, которые мы выбираем каждый раз, должны быть покрытой точкой и непокрытой точкой. Таким образом, дерево, которое мы генерируем бок о бок, а не лоскутное одеяло, как Крускал.
Давайте посмотрим на пример:
Мы соединили четыре точки ABCD, где длина CE равна 7, длина DF равна 9, а длина EF равна 5. Хотя длина EF меньше, чем CE, поскольку мы должны соединить покрытую точку и непокрытую точку,Хотя расстояние EF меньше, мы также не можем выбрать. Можно выбрать только CE, поэтому в процессе выполнения всего алгоритма дерево постепенно становится больше. Если это Kruskal, то мы обязательно сначала подключим EF, а потом подключим CE.В процессе работы всего алгоритма происходит разделение каждой части, а конечное дерево фактически "собирается" постепенно.
По сравнению с набором для обслуживания Kruskal мыГораздо проще, если точка обслуживания не закрыта. Поскольку выбранные ребра дерева не будут изменены, нам нужно использовать массив только для обозначения того, покрыты ли точки в каждой позиции или нет. Можно реализовать простой тип bool, что очень удобно.
Итак, остался только один вопрос: как сделать так, чтобы сумма путей генерируемого нами дерева была наименьшей?
Ответ Прим на этот вопрос, как и у Крускала, таков:жадный. Каждый раз, когда мы выбираем наименьшее ребро для расширения, Краскал сортирует все ребра, а затем оценивает, можно ли выбрать их по очереди. Так как же алгоритм Прима использует жадность?
На самом деле, это очень просто, и нам легко понять. Алгоритм Прима имеет ограничения на ребра и может выбирать ребра только между точками, которые были покрыты, и точками, которые не покрыты. Давайте дадим этим ребрам имя, называемоерасширяемый край. Тогда, очевидно, что нам нужно сделать, это выбрать самое короткое среди расширяемых ребер для увеличения.
Остался только один вопрос: как выбрать и сохранить кратчайшее увеличиваемое ребро, сортируется ли оно при каждой перезарядке?
Очевидно, что нет, поскольку сортировка каждый раз слишком затратна, мы можем использовать структуру данных для поддержки этих ребер и позволять им сортироваться в соответствии с длиной ребра. Мы должны быть знакомы с этой структурой данных, с которой мы сталкивались несколько раз:приоритетная очередь.
Ключ для нашей сортировки уже очевиден, то есть длина ребра, и суждение о том, законно ли ребро, тоже очень просто, нам нужно только судить, есть ли точки, которые не покрыты. Итак, весь процесс связан, мы можем сначала организовать процесс и написать его процесс:
选择一个点u，当做已经覆盖
把u所有相连的边加入队列
循环
循环 从队列头部弹出边
如果边合法
弹出
跳出循环
获取边的两个端点
将未覆盖的端点所有边加入队列
直到所有点都已经覆盖
Наконец, давайте посмотрим на реализацию Python, первая — это часть очереди приоритетов, эту логику мы можем использовать в готовом виде.heapqреализовать.
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
# 传入两个参数，一个是存放元素的数组，另一个是要存储的元素，这里是一个元组。
# heap内部默认从小到大排
heapq.heappush(self._queue, (priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
def empty(self):
return len(self._queue) == 0
Далее идет реализация алгоритма Прима, здесь для удобства хранения используемсписок смежностидля хранения информации о границах. Список смежности на самом деле представляет собой массив связанных списков, и каждый элемент массива является головным узлом связанного списка. Этот связанный список хранит всю информацию о ребрах узла.
Например, связанный список с индексом 1 в списке смежности хранит информацию обо всех ребрах, соединенных с узлом 1. Эта структура данных часто используется, когда мы храним деревья и графы, но она несложная, и нам не нужно реализовывать связанный список, потому что его можно имитировать массивом.
edges = [[1, 2, 7], [2, 3, 8], [2, 4, 9], [1, 4, 5], [3, 5, 5], [2, 5, 7], [4, 5, 15], [4, 6, 6], [5, 6, 8], [6, 7, 11], [5, 7, 9]]
if __name__ == "__main__":
# 记录点是否覆盖
visited = [False for _ in range(11)]
visited[1] = True
# 邻接表，可以理解成二维数组
adj_table = [[] for _ in range(11)]
# u和v表示两个端点，w表示线段长度
# 我们把v和w放入下标u中
# 把u和w放入下标v中
for (u, v, w) in edges:
adj_table[u].append([v, w])
adj_table[v].append([u, w])
que = PriorityQueue()
# 我们选择1作为起始点
# 将与1相邻的所有边加入队列
for edge in adj_table[1]:
que.push(edge, edge[1])
ret = 0
# 一共有7个点，我们需要加入6条边
for i in range(7):
# 如果队列为空，说明无法构成树
while not que.empty():
u, w = que.pop()
# 如果连通的端点已经被覆盖了，则跳过
if visited[u]:
continue
# 标记成已覆盖
visited[u] = True
ret += w
# 把与它相连的所有边加入队列
for edge in adj_table[u]:
que.push(edge, edge[1])
break
print(ret)
конец
На этом знакомство с алгоритмом Прима закончено. По сути, Прим и Крускал — это по сути две стороны алгоритма минимального остовного дерева, суть обоих одна и та же, то есть аугментация. Единственная разница в том, что один является увеличением точки, а другой — увеличением ребра. Однако, поскольку увеличение точек также зависит от ребер, Prim использует не только точки, чтобы судить о покрытии, но и информацию о ребрах для увеличения точек.
Если вы просто начинаете с логики алгоритма, и не можете понять его суть, то не только легко спутать два алгоритма, но и легко запутаться при написании кода, и не знать, что поддерживать, а что расширять.
ДополненныйИдея часто используется в алгоритмах, связанных с теорией графов (таких как сетевой поток), а не только в минимальном связующем дереве, поэтому понимание этой концепции очень важно для нашего последующего обучения. Я надеюсь, что каждый может понять суть этого.
Сегодняшняя статья здесь, оригинальность не из легких,Отсканируйте код, чтобы подписаться на менядля более замечательных статей.