PRIM求最小生成树

### PRIM算法最小生成树实现方法

#### 理论基础
PRIM算法是一种用于寻找加权无向图中的最小生成树的经典贪心算法。该算法通过逐步扩展一棵正在生长的树来构建最小生成树，每次都选择连接到当前树的一个最短边[^2]。

#### 朴素PRIM算法实现
对于稠密图而言，采用邻接矩阵表示法下的朴素PRIM算法效率较高。此版本的时间复杂度为O(V²)，其中V代表顶点的数量。以下是具体的Python代码实现：

import sys

def prim_mst(graph):
    V = len(graph)
    selected_node = [0]*V
    
    no_edge = 0
    selected_node[0] = True

    result = []
    
    while (no_edge < V - 1):        
        minimum = sys.maxsize
        x, y = 0, 0
        
        for i in range(V):
            if selected_node[i]:
                for j in range(V):
                    if ((not selected_node[j]) and graph[i][j]):  
                        if minimum > graph[i][j]:
                            minimum = graph[i][j]
                            x, y = i, j
                        
        print(str(x) + "-" + str(y) + ":" + str(graph[x][y]))
        result.append((x,y))
        selected_node[y] = True
        no_edge += 1
        
    return result

这段程序接收一个二维列表`graph`作为输入参数，它描述了一个带权重的无向图，在这个例子中使用的是邻接矩阵形式。函数返回的结果是一个由元组组成的列表，每个元组包含了构成MST的一条边及其两端节点编号[^1]。

#### 堆优化版PRIM算法
当处理稀疏图时，利用优先队列(通常用二叉堆实现)可以显著提高性能至接近线性的水平(O(E log V))。下面是改进后的C++代码片段展示如何应用这种技术:

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+7;
typedef pair<int,int> PII;
vector<PII> adj[MAXN];
int n,m,dist[MAXN],vis[MAXN];

void Prim(){
    priority_queue<PII,vector<PII>,greater<PII>> pq; 
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;pq.push({dist[1],1});
    
    long long sum=0;
    while(!pq.empty()){
        auto t=pq.top();pq.pop();
        int ver=t.second,w=t.first;
        if(vis[ver]) continue;
        vis[ver]=true;
        sum+=w;
        
        for(auto item :adj[ver]){
            int next=item.first,next_w=item.second;
            if(next_w<dist[next]&&!vis[next]){
                dist[next]=next_w;
                pq.push({dist[next],next});
            }
        }   
    }

}

上述代码展示了更高效的PRIM算法变体，适用于大规模网络分析场景下快速计算最小生成树问题。