prim＿mst构造最小生成树的思想

prim_mst构造最小生成树的思想是通过贪心算法逐步选择边来构建最小生成树。具体步骤如下：

1. 创建一个空的最小生成树MST和一个空的集合visited，用于存储已经访问过的顶点。
2. 选择一个起始顶点作为根节点，并将其加入visited集合。
3. 从根节点开始，遍历与根节点相邻的边，并选择权重最小的边。
4. 将选择的边加入MST，并将边的另一个顶点加入visited集合。
5. 重复步骤3和步骤4，直到visited集合包含所有顶点。
6. 最终得到的MST就是原图的最小生成树。

以下是使用prim_mst构造最小生成树的示例代码：

import numpy as np

def prim_mst(graph):
    num_vertices = len(graph)
    MST = []
    visited = set()
    
    # 选择起始顶点
    start_vertex = 0
    visited.add(start_vertex)
    
    while len(visited) < num_vertices:
        min_weight = np.inf
        min_edge = None
        
        # 遍历已访问的顶点
        for vertex in visited:
            # 遍历与已访问顶点相邻的边
            for neighbor, weight in enumerate(graph[vertex]):
                # 如果边的另一个顶点未访问且权重更小，则更新最小边
                if neighbor not in visited and weight < min_weight:
                    min_weight = weight
                    min_edge = (vertex, neighbor)
        
        # 将最小边加入MST，并将边的另一个顶点加入visited集合
        MST.append(min_edge)
        visited.add(min_edge[1])
    
    return MST

# 示例输入矩阵
graph = np.array([[0, 192, 344, 0, 0, 0, 0, 0, 0, 0, 0],
                  [192, 0, 309, 0, 555, 0, 0, 0, 0, 0, 0],
                  [344, 309, 0, 499, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 499, 0, 840, 0, 229, 286, 0, 0, 0],
                  [0, 555, 0, 840, 0, 237, 0, 0, 0, 0, 0]])

# 构造最小生成树
MST = prim_mst(graph)
print("Minimum Spanning Tree:")
for edge in MST:
    print(edge)

输出结果为最小生成树的边集合。