最小生成树prim邻接表

使用Prim算法在邻接表表示的图中构建最小生成树
理解Prim算法的核心概念
Prim算法是一种用于寻找加权连通图中的最小生成树的经典贪心算法。该方法通过逐步扩展已有的部分生成树，每次加入距离最近的一个新节点直到覆盖所有顶点[^1]。
数据结构的选择——邻接表
为了提高效率并节省空间，在处理稀疏图时通常会选择使用邻接表作为底层的数据结构来存储图形信息。对于每一个顶点v而言，仅需记录与其相连的所有其他顶点及其对应的权重即可形成一张完整的图表描述[^2]。
关键操作解析

初始化：选取任意一个起点s，并将其标记为访问过；创建优先队列Q用来保存待考察边缘列表。
迭代更新：从未被选入当前MST集合S内的那些结点u出发探索其相邻边(v,w)，如果w小于目前所知到达v的最佳路径长度，则更新此值并将[v,w]放入Q等待后续比较。
终止条件：当所有顶点都被纳入到正在生长着的部分生成树内时结束循环[^3]。

C++代码实例展示
下面给出一段基于上述原理编写的C++程序片段，展示了如何利用邻接表形式表达输入数据并通过执行Prim算法求得最终的结果：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> PII; // first: weight, second: vertex index

struct Edge {
int to;
int cost;
};

const int MAX_V = 1e5+7;
bool used[MAX_V];
int V,E,mincost=0;
vector<Edge> G[MAX_V];

void prim() {
priority_queue<PII,vector<PII>,greater<>> Q;

fill(used,used+V,false);
Q.push(make_pair(0,0));

while(!Q.empty()){
PII p = Q.top(); Q.pop();

int v=p.second;
if (used[v]) continue;
mincost += p.first;
used[v]=true;

for(auto e : G[v]){
if (!used[e.to])
Q.push(make_pair(e.cost,e.to));
}
}
}

int main(){
cin >> V >> E;
for(int i=0;i<E;++i){
int s,t,d;
cin >> s >> t >> d;
G[s].push_back((Edge){t,d});
G[t].push_back((Edge){s,d});
}

prim();

cout << "Minimum Spanning Tree Cost is:" <<mincost<< endl;
}
登录后复制