1075: 求最小生成树(Prim算法)
时间: 2023-07-22 14:38:54 浏览: 84
Prim算法是一种求解加权无向连通图的最小生成树的贪心算法。它从一个顶点开始,逐步扩展生成树的大小,直到生成整个最小生成树为止。
以下是Prim算法的实现过程:
1. 从图中任选一个顶点作为起始点,将该顶点加入生成树中。
2. 以该顶点为起始点,找出与其相邻的所有边,并将这些边加入到一个优先队列中。
3. 从队列中取出一条边(权值最小),如果该边的另一个端点不在生成树中,则将其加入生成树中,并将该点作为下一个起始点。
4. 重复步骤2和步骤3,直到生成树包含所有的顶点。
以下是Prim算法的C++代码实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1005;
const int INF = 1e9;
int n, m;
int vis[MAXN], dis[MAXN];
vector<pair<int, int>> G[MAXN]; //G[i]存储以i为起点的所有边
int Prim(int s)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //小根堆
fill(dis, dis + n + 1, INF); //初始化
dis[s] = 0;
pq.push(make_pair(0, s));
int sum = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
sum += dis[u];
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i].first;
int w = G[u][i].second;
if (!vis[v] && w < dis[v])
{
dis[v] = w;
pq.push(make_pair(dis[v], v));
}
}
}
return sum;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
G[u].push_back(make_pair(v, w));
G[v].push_back(make_pair(u, w));
}
int ans = Prim(1); //从1号点开始生成最小生成树
cout << ans << endl;
return 0;
}
```
其中,dis[i]表示以i为起点的最小边权值,vis[i]表示是否已经访问过i节点。优先队列pq存储以访问过的点为起点的边,每次取出队首元素时,若该点已经被访问过,则弃掉该边,否则将该点加入生成树中,并将该点的所有边加入队列中。