Kruskal & Prim C++实现

解题思路:最小生成树问题,可以用Kruskal或Prim算法解决。

Kruskal:

    算法思路:将图的边按升序排序,每次选择当前最小边,若加入该边不会构成回路,则加入。

    参考代码:

/*
 *Kruskal算法实现思路:
 *按边权重升序排序,每次取当前最小权重边(u,v),判断顶点(u,v)的加入是否会
 *形成环路,如果不形成则该边可以作为最小生成树的边,否则跳过
 *这里是否形成环路的判断可以用并查集实现 
 */
#include<cstdio>
#include<algorithm>
using namespace std;

const int Max_N = 50;

struct Edge//边结构体
{
	int u,v,w;
	Edge(){}
	Edge(int u_,int v_,int w_)
	{
		u = u_; v = v_; w = w_; //构造函数 
	}
	bool operator < (const Edge& e) const
	{
		return w<e.w;   
	}
}edge[Max_N*Max_N];  //E<=V^2

int n;
/* 并查集  */
int par[Max_N]; //父亲 
int height[Max_N];  //树的高度(为压缩路径) 
void init(int n); //初始化 
int find( int x ); //x的父亲
void unite( int x, int y ); //合并x,y
bool same( int x, int y); //x,y是否在同一组 
/* 并查集 */ 
void MST_Kruskal(Edge *, int );

int main()
{
	scanf("%d",&n); 
	int index = 0;
	for( int i=0; i<n; i++ )
	{
		for( int j=0; j<n; j++ )
		{
			int w;
			scanf("%d",&w);
			if( i0 ) //i<j 因为是对称矩阵,只需取一半 且i==j时w==0 
			{
				edge[index++] = Edge(i,j,w);
			}
		}
	}
	
	MST_Kruskal(edge,index);
	
	return 0;
}

void init(int n)
{
	for( int i=0; i<n; i++ )
	{
		par[i] = i;
		height[i] = 0;
	}
}

int find( int x )
{
	return x==par[x] ? x : par[x] = find( par[x] );
}

void unite( int x, int y )
{
	x = find( x );	y = find( y );
	if( x==y )
		return;
	if( height[x]<height[y] )
	{
		par[x] = y;
	}
	else
	{
		par[y] = x;
		if( height[x]==height[y] )	height[x]++;
	}
}

bool same( int x , int y )
{
	return find(x)==find(y);
}

void MST_Kruskal(Edge *edge, int length )
{
	/*初始化*/
	init(n);
	sort(edge,edge+length);
	
	int cnt = 0, res = 0;
	for( int i=0; i<length; i++ )
	{
		int u = edge[i].u, v = edge[i].v, w = edge[i].w;
		if( same(u,v) )	continue;  //已经在同一颗树中,如果再加入(u,v)会形成回路
		
		res += w;
		unite(u,v); //加入同一组(可以认为同一个联通分量中) 
		cnt++;
		
		if( cnt==n-1 )	break; //边的数目只需n-1 
	}
	
	printf("%d\n",res);
}

Prim:

    算法思路:与Dijkstra算法类似,保存一个集合作为当前最小生成树的顶点子集A,每次选取连接A与V-A的最小权重的边,并将边的顶点加入集合A中。

并以该顶点更新与之相连的V-A中顶点的权重key值。

    参考代码:

/*
 *最小生成树:Prim算法实现
 *题目仅仅要求最小生成树代价,所以可以简单实现,不用记录树的结构
 *Prim算法思想:最小生成树子集A始终为一颗树,
 *每次在V-A中找安全便加入A中
 *其快速实现是给每个顶点一个权重,表示其到A的最短距离,若无连接则为INF
 *可以用有限队列保存,每次取key最小 
 *这里因暂时不会在C++中实现对队列中某一元素值的快速更新,所以采用
 *全局变量key保存且可能在pqueue中可能会有重复顶点 所以增加一段代码以删除重复结点 
 */
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

const int INF   = 1e8;
const int Max_N = 50; 

struct Vertex//顶点 
{
	int v;
	int key;
	Vertex( int v_, int key_ ){v = v_; key = key_;}
	bool operator<(const Vertex &ver) const
	{
	    return key>ver.key;
	}
};

struct Edge//边 
{
	int to;
	int w;
	Edge(int to_, int w_ ){to = to_; w = w_;}
};

int n;
int key[Max_N];       //每个顶点的权重  
bool visited[Max_N];  //快速判断顶点是否已经在集合A中 
vector<Edge> graph[Max_N];  //带权邻接图(适合稀疏图)

void MST_Prim( int r , int n )
{
	/*初始化*/ 
	for( int i=0; i<n; i++ )
	{
		key[i]	   = INF;
		visited[i] = false;
	}
	
	key[r] = 0;
	priority_queue<Vertex> pque;  //A中顶点 
	Vertex temp_v = Vertex(r,0);
	pque.push( temp_v );
	
	while( pque.size() )
	{
		while( pque.size() && visited[pque.top().v] )
		{
			pque.pop(); //可能出现重复顶点如队列情况 
		}
		if( pque.empty() )	break;
		
		Vertex cur_v = pque.top(); pque.pop();
		int v = cur_v.v;
		visited[v] = true;
		
		for( int i=0; i<graph[v].size(); i++ )
		{
			int u = graph[v][i].to;
			int key_ = graph[v][i].w;
			if( !visited[u] && key_<key[u] )
			{
				key[u] = key_;
				pque.push( Vertex(u,key_) );
			}
		}
	}
}

void solve()
{
	MST_Prim(0,n);
	int res = 0;
	for( int i=0; i<n; i++ )	res += key[i];
	printf("%d\n",res);
}

int main()
{
	scanf("%d",&n);
	for( int i=0; i<n; i++ )
	{
		for( int j=0; j<n; j++ )
		{
			int w;
			scanf("%d",&w);
			if( w>0 )	graph[i].push_back( Edge(j,w) );
		}
	}
	
	solve();
	
	return 0;
}