首页采用Prim算法或者Kruskal算法实现从图中构造最小生成树过程。返回完整代码

采用Prim算法或者Kruskal算法实现从图中构造最小生成树过程。返回完整代码

时间: 2024-11-05 17:24:11 浏览: 64

Prim算法和Kruskal算法都是用于寻找无向加权连通图的最小生成树的经典算法。下面我会简要解释并提供这两种算法的基本Python实现。 **Prim算法**（也叫Prim-Johnson算法）：该算法从图的一个顶点开始，逐步添加边，每一步选择当前未加入的节点中距离已形成树中最近的那个节点。以下是简单的Python版本： ```python import heapq def prim(graph, start): visited = {start: 0} edges = [(weight, u, v) for u in graph for (v, weight) in graph[u].items()] heap = [(0, start)] while heap: weight, current_node = heapq.heappop(heap) if current_node not in visited: visited[current_node] = weight for neighbor, edge_weight in graph[current_node].items(): if neighbor not in visited: heapq.heappush(heap, (edge_weight, neighbor)) return visited ``` **Kruskal算法**： Kruskal算法则是从小到大遍历所有边，只选择不会形成环路的一组边来构建树。这里同样是一个基本的Python实现： ```python def kruskal(graph): result = [] edges = sorted((weight, u, v) for u in graph for (v, weight) in graph[u].items()) set_of_vertices = set(range(len(graph))) while len(result) < len(graph)-1 and set_of_vertices: weight, u, v = edges.pop(0) if u != v and {u, v} <= set_of_vertices: result.append((u, v, weight)) set_of_vertices.remove(u) set_of_vertices.remove(v) return result ``` 上述代码假设`graph`是一个邻接权重字典，键表示节点，值是另一个字典，键值对代表相邻节点及其边的权重。

阅读全文