Источник: https://shawnlyu.com/algorithms/minimum-spanning-tree-prim/
Минимальное остовное дерево (MST) или остовное дерево с минимальным весом — это подмножество ребер связанного, реберно- взвешенный неориентированный граф, соединяющий все вершины вместе, без циклов и с минимально возможным суммарным весом ребер.
В этом посте будет представлен один из алгоритмов поиска MST: Prim. Будут предоставлены логика, пространственно-временные сложности и реализации. Подвиг. Литкод вызова 1584. Минимальная стоимость подключения всех точек.
Логика
Логика Прима очень похожа на алгоритм Дейкстры, который также жадно находит самое легкое ребро. Он начинается с произвольной вершины v и заканчивается набором ребер A, охватывающих все вершины. На каждом шаге он будет искать ребро, соединяющее A с изолированной вершиной в графе. Псевдокод показан ниже.
MST-PRIM(G,w,r)
'''
G: the connected graph
w: weights
r: the root vertex
Q: a min-priority queue based on a key field
key: for each vertex v, key[v] is the minimum weight \
of any edge connecting to a vertex in the MST
π: for each vertex v, π[v] names the parent of v in the MST
'''
for each u in V[G]
key[u] = inf
π[u] = NIL
key[r] = 0
Q = V[G]
while Q:
u = EXTRACT_MIN(Q)
for each v in Adj[u]
if v in Q and w(u,v)<key[v]
π[v] = u
key[v] = w(u,v)
Вот иллюстрация для Prim:
Сложности
Существует два способа реализации строки 17.
- используя матрицу смежности, так что EXTRACT_MIN занимает O(V);
- с использованием двоичной кучи, так что EXTRACT_MIN занимает O(logV).
Матрица смежности
- Инициализация занимает O(V) (строки 11–15).
- Строка 16 будет выполняться в течение O(V) времени, поэтому EXTRACT_MIN занимает O(V∗ V) всего.
- Поскольку цикл while в строке 16 будет выполняться для каждой вершины, а цикл for в строке 18 будет выполняться для каждого ребра вершины, поэтому цикл for в строке 18 будет выполняться для O(E) раз.
Следовательно, общая временная сложность будет O(V+V^2+E)= O(V^2). Сложность пространства будет O(V+E).
Двоичная куча
- Инициализация занимает O(V) (строки 11–15).
- Строка 16 будет выполняться в течение O(V) времени, поэтому EXTRACT_MIN занимает O(V∗ logV) всего.
- Поскольку цикл while в строке 16 будет выполняться для каждой вершины, а цикл for в строке 18 будет выполняться для каждого ребра вершины, поэтому цикл for в строке 18 будет выполняться для O(E) раз.
- Строка 21 указывает на операцию обновления кучи, поэтому принимает logV.
Следовательно, общая временная сложность составит O(V+VlogV+ElogV)=O(ElogV). Сложность пространства будет O(V+E).
Реализации — 1584. Минимальная стоимость подключения всех точек
Будут предоставлены две реализации, использующие двоичную кучу и матрицу смежности. Заметив, что этот граф является плотным, следовательно, использование двоичной кучи дает O(ElogV)=O(V^2logV), а использование матрицы смежности дает O(V^2). Следовательно, последний будет более эффективным решением.
Двоичная куча
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
dist = collections.defaultdict(list)
n = len(points)
for i in range(n):
for j in range(i+1,n):
d = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])
dist[i].append((j,d))
dist[j].append((i,d))
ret = 0
visited = set([])
pq = [(0,0)]
while pq:
w,u = heapq.heappop(pq)
if u not in visited:
ret += w
visited.add(u)
for v,d in dist[u]:
if v not in visited: heapq.heappush(pq,(d,v))
return ret
Матрица смежности
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
def dist(u,v):
return abs(points[u][0]-points[v][0])+abs(points[u][1]-points[v][1])
n = len(points)
ret = 0
visited = [False]*n
visited[0] = True
closest = [0]*n
for i in range(1,n): closest[i] = dist(0,i)
for _ in range(n-1):
mini = float('inf')
node = -1
for i in range(n):
if not visited[i] and closest[i] < mini:
mini = closest[i]
node = i
ret += mini
visited[node] = True
for i in range(n):
if not visited[i]: closest[i] = min(closest[i],dist(i,node))
return ret
