普里姆算法形成最小生成树代码

### 实现普里姆算法以构建最小生成树

为了实现普里姆算法 (Prim’s Algorithm)，用于寻找加权无向图中的最小生成树，下面提供了一个Python版本的实现方法[^1]。

import sys  
from collections import defaultdict  

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 
    # the set of vertices not yet included in shortest path tree 
    def minKey(self, key, mstSet): 
        
        # Initialize min value 
        min_val = sys.maxsize 
        min_index = None
  
        for v in range(self.V): 
            if key[v] < min_val and mstSet[v] == False: 
                min_val = key[v] 
                min_index = v 
  
        return min_index 
  
    # Function to construct and print MST for a graph represented using adjacency matrix representation 
    def primMST(self): 

        # Key values used to pick minimum weight edge in cut 
        key = [sys.maxsize] * self.V 
        parent = [None] * self.V  # Array to store constructed MST 
        key[0] = 0   # Make key 0 so that this vertex is picked as first vertex 
        mstSet = [False] * self.V 
  
        parent[0] = -1  # First node is always root of MST 
  
        for cout in range(self.V): 

            # Pick the minimum distance vertex from the set of vertices not yet processed. u is always equal to src in first iteration 
            u = self.minKey(key, mstSet) 
  
            # Put the minimum distance vertex in the shortest path tree 
            mstSet[u] = True
            
            # Update dist value of the adjacent vertices of the picked vertex only if the current distance is greater than new distance and the vertex in not in the shotest path tree 
            for v in range(self.V): 
                # graph[u][v] is non zero only for adjacent vertices of m 
                # mstSet[v] is false for vertices not yet included in MST 
                # Update the key only if graph[u][v] is smaller than key[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 the constructed MST 
        self.printMST(parent)

    def printMST(self, parent): 
        print ("Edge \tWeight")
        for i in range(1, self.V): 
            print (parent[i], "-", i, "\t", self.graph[i][parent[i]])

此代码定义了一个`Graph`类，其中包含了初始化函数、找到集合中具有最小键值顶点的方法以及执行普里姆算法并打印结果的主要功能。注意，在实际应用这段代码之前应当仔细测试其正确性和性能表现[^3]。