实现最小生成树的算法：普里姆算法、克鲁斯卡尔算法

最小生成树是指在一个连通图中，找到一棵包含所有顶点且权值最小的生成树。普里姆算法和克鲁斯卡尔算法都是常用的求解最小生成树的算法。

1. 普里姆算法：
- 算法思路：
- 从图中任意选择一个顶点作为起始点，将其加入最小生成树中。
- 从已加入最小生成树的顶点集合中，选择一个顶点v，将与v相连的边中权值最小的边(u, v)加入最小生成树中，并将顶点u加入最小生成树的顶点集合中。
- 重复上一步，直到最小生成树包含了图中所有的顶点。
- 算法实现（邻接矩阵存储）：

     def prim(graph):
         num_vertices = len(graph)
         selected = [False] * num_vertices
         selected[0] = True
         for _ in range(num_vertices - 1):
             min_weight = float('inf')
             u, v = -1, -1
             for i in range(num_vertices):
                 if selected[i]:
                     for j in range(num_vertices):
                         if not selected[j] and graph[i][j] < min_weight:
                             min_weight = graph[i][j]
                             u, v = i, j
             selected[v] = True
             print(f"Add edge ({u}, {v}) with weight {min_weight} to the minimum spanning tree.")
     
     # 示例图的邻接矩阵表示
     graph = [
         [0, 2, 0, 6, 0],
         [2, 0, 3, 8, 5],
         [0, 3, 0, 0, 7],
         [6, 8, 0, 0, 9],
         [0, 5, 7, 9, 0]
     ]
     
     prim(graph)

2. 克鲁斯卡尔算法：
- 算法思路：
- 将图中的所有边按照权值从小到大进行排序。
- 依次选择权值最小的边，如果这条边的两个顶点不在同一个连通分量中，则将这条边加入最小生成树中，并将这两个顶点合并到同一个连通分量中。
- 重复上一步，直到最小生成树包含了图中所有的顶点。
- 算法实现（邻接表存储）：

     class Edge:
         def __init__(self, src, dest, weight):
             self.src = src
             self.dest = dest
             self.weight = weight
     
     class Graph:
         def __init__(self, num_vertices):
             self.num_vertices = num_vertices
             self.edges = []
     
         def add_edge(self, src, dest, weight):
             self.edges.append(Edge(src, dest, weight))
     
     def find(parent, i):
         if parent[i] == i:
             return i
         return find(parent, parent[i])
     
     def union(parent, rank, x, y):
         xroot = find(parent, x)
         yroot = find(parent, y)
         if rank[xroot] < rank[yroot]:
             parent[xroot] = yroot
         elif rank[xroot] > rank[yroot]:
             parent[yroot] = xroot
         else:
             parent[yroot] = xroot
             rank[xroot] += 1
     
     def kruskal(graph):
         result = []
         i, e = 0, 0
         graph.edges = sorted(graph.edges, key=lambda x: x.weight)
         parent = []
         rank = []
         for node in range(graph.num_vertices):
             parent.append(node)
             rank.append(0)
         while e < graph.num_vertices - 1:
             edge = graph.edges[i]
             i += 1
             x = find(parent, edge.src)
             y = find(parent, edge.dest)
             if x != y:
                 e += 1
                 result.append(edge)
                 union(parent, rank, x, y)
         for edge in result:
             print(f"Add edge ({edge.src}, {edge.dest}) with weight {edge.weight} to the minimum spanning tree.")
     
     # 示例图的邻接表表示
     graph = Graph(5)
     graph.add_edge(0, 1, 2)
     graph.add_edge(0, 3, 6)
     graph.add_edge(1, 2, 3)
     graph.add_edge(1, 3, 8)
     graph.add_edge(1, 4, 5)
     graph.add_edge(2, 4, 7)
     graph.add_edge(3, 4, 9)
     
     kruskal(graph)