最小生成树定义：

  • 在一个给定的无向图中，求一棵树使得这棵树拥有图中所有的顶点
  • 所有边都是来自图中的边
  • 满足整棵树的边权之和最小

最小生成树性质：

  • ①最小生成树是树，因此其边数等于顶点数减一，且树内一定不会有环
  • ②对给定的图，其最小生成树可以不唯一，但其边权之和一定是唯一的
  • ③由于最小生成树是在无向图上生成的，因此其根结点可以是这棵书上的任意一个结点，题目中涉及到最小生成树本身的输出，为了使最小生成树唯一，一般都会直接给出根结点，题目中涉及到最小生成树边权输出，边权之和一样

prim算法

  • 用来解决最小生成树问题
  • prim算法与DIjkstra算法思想几乎一致
  • DIjkstra算法：起点s到顶点d的最短距离
  • prim算法：起点s到集合d的最短距离，默认起点为0或者1

prim算法代码实现

int n,map[maxn][maxn];
int d[maxn];
int vis[maxn];

int prim(){
   
	mm(d,inf);
	d[0]=0;
	int ans=0;//存放最小生成树边权之和
	for(int i=0;i<n;i++){
   
		int u=-1,minn=inf;
		for(int j=0;j<n;j++){
   
			if(!vis[j]&&d[j]<minn){
   
				u=j;
				minn=d[j];
			}
		}
	if(u==-1) return -1;
	vis[u]=1;
	ans+=d[u];
	for(int v=0;v<n;v++){
   
		//v未访问&&u能到达v&&以u为中介点可以使v离集合S更近 
		if(!vis[v]&&map[u][v]!=inf&&map[u][v]<d[v]){
   
			d[v]=map[u][v];
		}
	}
	}
	return ans; 
}

题目链接：

公路村村通 (30分)