JZTXT

最小生成树学习笔记

发布时间 2023-08-17 08:19:11作者: ccrui

Prim算法

prim算法基本思想：对图 \(G(V,E)\) 设置集合S来存放已被访问的顶点，然后执行 \(n\) 次下面的两个步骤( \(n\)为顶点个数)

  1. 每次从集合 \(V-S\) 中选择与集合S最近的一个顶点(记为 \(u\) )，访问 \(u\) 并将其加入集合S，同时把这条离集合 \(S\) 最近的边加入最小生成树。
  2. 令顶点 \(u\) 作为集合 \(S\) 与集合 \(V-S\) 连接的接口，优化从 \(u\) 能到达的未访问顶点 \(v\) 与集合 \(S\) 的最短距离
struct point{
	int d,s;
	bool operator < (const point &a) const {
	    return s > a.s;
	}
};
vector<point>v[50100];
int prim(){
	int ans=0;
	for(int i=1;i<=n;i++)dis[i]=1e9;
	priority_queue<point>q;
	dis[1]=0;
	q.push(point{1,0});
	while(!q.empty()&&c<n){
		int u=q.top().d;
		q.pop();
		if(!b[u]){
			c++;
			b[u]=1;
			for(int i=0;i<v[u].size();i++){
				int d=v[u][i].d,s=v[u][i].s;
				//cout<<d<<" "<<s<<' '<<dis[d]<<endl;
				if(!b[d]&&dis[d]>s){
					dis[d]=s;
					q.push(point{d,dis[d]});
				}
			}
			ans+=dis[u];
		}
	}
	//cout<<c<<endl;
	if(c==n)return ans;
	else return -1;
}

Kruskal

  1. 初始化。将所有边都按权值从小到大排序，将每个节点集合号都初始化为自身编号。

  2. 按排序后的顺序选择权值最小的边 \(（u,v）\)。

  3. 如果节点 \(u\) 和 \(v\) 属于两个不同的连通分支，则将边 \((u,v)\) 加入边集 \(TE\) 中，并将两个连通分支合并。

  4. 如果选取的边数小于 \(n-1\) ,则转向步骤2，否则算法结束。