Prim算法是最小边

### Prim算法与最小生成树

#### 最小生成树概念
在一个连通无向加权图中，如果选取若干条边构成一棵树，使得这棵树包含原图中的所有顶点，并且这些边的权重之和尽可能小，则该树称为最小生成树(Minimum Spanning Tree, MST)[^1]。

#### Prim算法概述
Prim算法是一种用于构建最小生成树的有效方法之一。此算法通过逐步扩展已有的部分生成树来工作，在每一步都选择连接到当前生成树最近的一个未访问节点作为新的成员加入其中[^2]。

#### 算法特点
- **贪心策略**：始终挑选距离现有生成树最短路径上的下一个结点。
- **局部最优解组合成全局最优解**：每一次迭代都是为了找到最佳的选择以确保最终形成的MST具有最低可能的成本。

#### 应用场景
Prim算法广泛应用于网络设计领域，比如电信线路铺设、计算机局域网组建等问题上；另外也适用于解决一些实际生活中的问题，如城市供水管道规划等，旨在减少材料成本的同时保证系统的连通性和稳定性。

#### 朴素版Prim算法实现
下面给出Python语言下的简单版本Prim算法代码：

import sys 

def prim(graph): 
    n = len(graph) 
    selected_node = [0]*n  
    no_edge = 0 
    selected_node[0] = True 
    
    print("Edge : Weight\n") 
    while (no_edge < n - 1): 
        
        minimum = sys.maxsize 
        a = 0 
        b = 0 
        for m in range(n): 
            if selected_node[m]: 
                for n in range(n): 
                    if ((not selected_node[n]) and graph[m][n]):   
                        if minimum > graph[m][n]: 
                            minimum = graph[m][n] 
                            a = m 
                            b = n 
        print(str(a) + "-" + str(b) + ":" + str(graph[a][b])) 
        selected_node[b] = True 
        no_edge += 1
        
# 示例输入矩阵表示带权邻接表形式的图
graph = [[0, 28, 0, 0, 0, 10],
         [28, 0, 16, 0, 0, 0], 
         [0, 16, 0, 12, 0, 0], 
         [0, 0, 12, 0, 22, 0], 
         [0, 0, 0, 22, 0, 25], 
         [10, 0, 0, 0, 25, 0]]
prim(graph)