无向图最小生成树算法

### 无向图最小生成树算法实现方法 #### Prim算法简介 Prim算法是一种用于寻找加权连通图的最小生成树的经典算法。该算法通过逐步扩展一棵初始为空的树来构建最小生成树，每次迭代都会选择一条连接已选节点集合与其他未加入节点之间的最短边。 #### 算法流程描述 对于给定的一个带权重的无向连通图 \( G=(V,E) \)，其中\( V \)表示顶点集而\( E \)代表边集： - 初始化阶段选取任意一个起点作为当前部分生成树的一部分； - 接着重复执行下述操作直到所有顶点都被纳入到正在生长中的这棵树里： - 查找并添加能够使得新旧两部分之间距离最近的那个尚未访问过的邻接结点及其对应的那条边至现有结构之中； 此过程确保每一步都遵循局部最优解原则从而最终获得全局最佳方案即整个网络内的最低总成本路径组合[^1]。 #### Python代码实例展示 下面给出一段基于Python编写的简单版本Prim算法实现，适用于处理稀疏矩阵形式存储的数据输入情况: ```python import sys class Graph(): def __init__(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)] for row in range(vertices)] # A utility function to find the vertex with minimum distance value, # from set of vertices not yet included in shortest path tree. def minKey(self, key, mstSet): # Initialize min value as infinite and index variable 'min_index'=-1 min_val = float('inf') min_index = -1 for v in range(self.V): if (key[v]<min_val)and(not mstSet[v]): min_val=key[v] min_index=v return min_index # Function to construct MST using prim's algorithm def primMST(self): # Array to store constructed MST parent=[None]*self.V # Key values used to pick minimum weight edge in cut key =[float('inf')]*self.V # To represent whether a node is part of MST or not mstSet=[False]*self.V # Include first vertex in MST key[0]=0 parent[0]=-1 # First node is always root of MST for cout in range(self.V): u=self.minKey(key,mstSet) mstSet[u]=True for v in range(self.V): if ((self.graph[u][v]>0)and(mstSet[v]==False)and(key[v]>self.graph[u][v])): key[v]=self.graph[u][v] parent[v]=u print ("Edge\tWeight") sum=0 for i in range(1,self.V): print(parent[i],"-",i,"\t",self.graph[i][parent[i]]) sum+=self.graph[i][parent[i]] print("\nMinimum Spanning Tree Weight:",sum) g = Graph(5) g.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 ]] g.primMST() ``` 上述程序展示了如何利用二维列表模拟邻接矩阵的方式来表达各个城市间道路长度关系，并调用了`primMST()`函数计算出了对应于这些城市的最小耗费旅行路线规划结果[^4]。