最小成本生成樹
有三種方法
Minimum Spanning Tree 最小成本生成樹
併查集 Disjoint Set 與 Union Find
python
for _ in range(int(input())):
edges = [edge.split(",") for edge in input().split()]
edges.sort(key=lambda x: int(x[2]))
parents = list(range(0, 26))
def find(x): # 找到老大並回傳
if x == parents[x]:
return x
parents[x] = find(parents[x]) # 因為只會記得上一個老大，所有要一直找，找到最大的那個
return parents[x]
def union(x, y): # 合併
x = find(x)
y = find(y)
parents[x] = y
cost = 0
for edge in edges:
u = ord(edge[0]) - 65 # 轉ascii 跟parent 有關，以A為基準
v = ord(edge[1]) - 65
if find(u) != find(v):
union(u, v) # 把 u 變成v的老大
cost += int(edge[2])
print(cost)Dijkstra’s Algorithm
Minimum Spanning Tree 最小成本生成樹
Prim's Algorithm
python
from collections import defaultdict
for _ in range(int(input())):
edges = [i.split(',') for i in input().split()]
# 建圖
graph = defaultdict(list) # 雙向
for i in edges:
graph[i[0]].append([i[1], int(i[2])])
graph[i[1]].append([i[0], int(i[2])])
# graph[i[0]] = graph.get(i[0],[]) + [[i[1], int(i[2])]]
# graph[i[1]] = graph.get(i[1],[]) + [[i[0], int(i[2])]]
print(graph)
# 排序values
for i in graph:
graph[i].sort(key=lambda x: x[1])
ans = []
visited = [edges[0][0]]
while len(visited) < len(graph):
min_edge = [0, 0, float('inf')]
for i in visited:
for j in graph[i]:
if (j[1] < min_edge[2]) and (j[0] not in visited):
min_edge = [i, j[0], j[1]]
ans.append(min_edge)
visited.append(min_edge[1])
# print(visited)
# print(min_edge)
# print(ans)
print(sum([i[2] for i in ans]))
# {'A': [['B', 6], ['E', 9], ['F', 12]],
# 'B': [['C', 3], ['D', 5], ['A', 6], ['F', 8]],
# 'C': [['B', 3], ['D', 7]],
# 'D': [['B', 5], ['C', 7], ['E', 10], ['F', 11]],
# 'E': [['A', 9], ['D', 10], ['F', 15]],
# 'F': [['B', 8], ['D', 11], ['A', 12], ['E', 15]]}Contributors
lucashsu95