本文主要是介绍图论-最小生成树-贪心，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最小生成树

概念

在所有图所形成的生成树中边权值最小的
生成树条件：
1.包含联通图的n个顶点，n-1条边
2.移除任何一条边都会导致不联通
3.生成树中不包括环

堆优化的prim算法（vector模拟邻接表）

prim要素
任意从一个点开始，每次选出一个未用点到已用点最短的点，以此点来更新其他点到已用点的距离。每次循环确定一个点。与dij不同的是dis维护的不同，一个是到起点的最短距离， 一个是到已用点的最短距离。

• 与dij一样，visit[MAXN]
• dis[MAXN],用来维护未用点到已用点集合的最短距离
  我采用vector模拟邻接表方式求解最短路模板

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct edge{
	int v;
	int dis;
};
vector<edge> myv[5002];
struct node{
	int pos;
	int dis;
	bool operator<(const node &x) const{
		return dis > x.dis;
	}
};
int n, m, u, v, w, sum, cnt;
int dis[5002], visit[5002];
priority_queue<node> mypq;
void prime(){
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	mypq.push(node{1, 0});
	while(!mypq.empty() && cnt < n){
		node temp = mypq.top();
		mypq.pop();
		int u = temp.pos, d = temp.dis;
		if(visit[u]){
			continue;
		}
		visit[u] = 1;
		cnt++;
		sum += d;
		for(int i = 0; i < myv[u].size(); i++){
			int v = myv[u][i].v;
			int w = myv[u][i].dis;
			if(visit[v]){
				continue;
			}
			if(dis[v] >  w){
				dis[v] = w;
				mypq.push(node{v, dis[v]});
			}
		}
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d", &u, &v, &w);	
		myv[u].push_back(edge{v, w});
		myv[v].push_back(edge{u, w});
	}
	prime();
	if(cnt == n){
		printf("%d", sum);
	}
	else{
		printf("orz");
	}
    return 0;
}

这篇关于图论-最小生成树-贪心的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！