edges = [
("Pe", "T", 13),
("Pe", "N", 68),
("Pe", "M", 78),
("Pe", "L", 51),
("Pe", "Pa", 51),
("T", "N", 68),
("T", "M", 70),
("T", "L", 60),
("T", "Pa", 61),
("N", "M", 21),
("N", "L", 35),
("N", "Pa",36),
("M", "L", 56),
("M", "Pa", 57),
("L", "Pa", 21),
]
class UnionFind:
def init(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def kruskal(edges):
edges.sort(key=lambda edge: edge[2])
uf = UnionFind(len(set(city for edge in edges for city in edge[:2])))
mst = []
for u, v, weight in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, weight))
return mst
city_map = {
"Pe": 0, "T": 1, "N": 2, "M": 3, "L": 4, "Pa": 5
}
edges_with_indices = [(city_map[u], city_map[v], weight) for u, v, weight in edges]
mst_edges = [(list(city_map.keys())[u], list(city_map.keys())[v], weight) for u, v, weight in kruskal(edges_with_indices)]
print("最小生成树的边:")
for u, v, weight in mst_edges:
print(f"{u} - {v}: {weight}")
print("2023310143005")
