C++编程练习(10)----“图的最小生成树“（Prim算法、Kruskal算法）

1、Prim 算法

以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。

2、Kruskal 算法

直接寻找最小权值的边来构建最小生成树。

比较：

Kruskal 算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势。

Prim 算法针对顶点展开，对于稠密图，即边数非常多的情况下会更好。

具体代码如下：

/* Graph.h头文件 */

/*包含图的建立：图的深度优先遍历、图的广度优先遍历*/

/*包含图的最小生成树：Prim 算法、Kruskal 算法*/

#include<iostream>

#include"LinkQueue.h"

#define MAXVEX 100

#define MAXEDGE 100

#define INFINITY 65535

#define TRUE 1

#define FALSE 0

typedef char VertexType;

typedef int EdgeType;

typedef int Boolean;

using namespace std;

/*邻接矩阵方式建立图*/

class MGraph{

public:

	VertexType vexs[MAXVEX];

	EdgeType arc[MAXVEX][MAXVEX];

	int numVertexes,numEdges;

};

/*建立无向网图的邻接矩阵表示*/

void CreateMGraph(MGraph *G)

{

	int i,j,k,w;

	cout<<"输入顶点数和边数："<<endl;

	cin>>G->numVertexes>>G->numEdges;

	cin.clear();

	cout<<"输入顶点信息："<<endl;

	for(i=0;i<G->numVertexes;i++)

	{

		cin>>G->vexs[i];

		cin.clear();

	}

	for(i=0;i<G->numVertexes;i++)

		for(j=0;j<G->numVertexes;j++)

		{

			if (i==j)

				G->arc[i][j]=0;

			else

				G->arc[i][j]=INFINITY;

		}

	for(k=0;k<G->numEdges;k++)

	{

		cout<<"输入边（vi,vj）上的下标i，下标j和权w:"<<endl;

		cin>>i>>j>>w;

		cin.clear();

		G->arc[i][j]=w;

		G->arc[j][i]=G->arc[i][j];

	}

}

/*邻接矩阵的深度优先递归算法*/

Boolean visited[MAXVEX];	/*访问标志的数组*/

void DFS(MGraph G,int i)

{

	int j;

	visited[i]=TRUE;

	cout<<G.vexs[i];	/*打印顶点，也可以其他操作*/

	for(j=0;j<G.numVertexes;j++)

		if(G.arc[i][j]==1 && !visited[j])

			DFS(G,j);	/*对为访问的邻接顶点递归调用*/

}

/*邻接矩阵的深度优先遍历操作*/

void DFSTraverse(MGraph G)

{

	cout<<"\n深度优先遍历结果为："<<endl;

	int i;

	for(i=0;i<G.numVertexes;i++)

		visited[i]=FALSE;	/*初始化所有顶点状态都是未访问过状态*/

	for(i=0;i<G.numVertexes;i++)

		if(!visited[i])	/*对未访问过的顶点调用DFS，若是连通图，只会执行一次*/

			DFS(G,i);

	cout<<endl;

}

/*邻接矩阵的广度遍历算法*/

void BFSTraverse(MGraph G)

{

	cout<<"广度优先遍历结果为："<<endl;

	int i,j;

	LinkQueue Q;

	for(i=0;i<G.numVertexes;i++)

		visited[i]=FALSE;

	for(i=0;i<G.numVertexes;i++)

	{

		if(!visited[i])

		{

			visited[i]=TRUE;

			cout<<G.vexs[i];

			Q.EnQueue(i);

			while(!Q.QueueEmpty())

			{

				Q.DeQueue(&i);

				for(j=0;j<G.numVertexes;j++)

				{

					if(G.arc[i][j]==1 && !visited[j])

					{

						visited[j]=TRUE;

						cout<<G.vexs[j];

						Q.EnQueue(j);

					}

				}

			}

		}

	}

	cout<<endl;

}

/* Prim算法生成最小生成树 */

void MiniSpanTree_Prim(MGraph G)

{

	cout<<"Prim算法生成最小生成树，结果为："<<endl;

	int min,i,j,k;

	int adjvex[MAXVEX];

	int lowcost[MAXVEX];

	lowcost[0]=0;

	adjvex[0]=0;

	for(i=1;i<G.numVertexes;i++)

	{

		lowcost[i]=G.arc[0][i];

		adjvex[i]=0;

	}

	for(i=1;i<G.numVertexes;i++)

	{

		min=INFINITY;

		j=1;k=0;

		while(j<G.numVertexes)

		{

			if(lowcost[j]!=0 && lowcost[j]<min)

			{

				min=lowcost[j];

				k=j;

			}

			j++;

		}

		cout<<"("<<adjvex[k]<<","<<k<<")"<<endl;

		lowcost[k]=0;

		for(j=1;j<G.numVertexes;j++)

		{

			if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j])

			{

				lowcost[j]=G.arc[k][j];

				adjvex[j]=k;

			}

		}

	}

	cout<<endl;

}

/* Kruskal 算法生成最小生成树 */

class Edge{		/*对边集数组Edge结构的定义*/

public:

	int begin;

	int end;

	int weight;

};

void Swap(Edge *edges,int i,int j)		/* 交换权值 以及头和尾 */

{

	int temp;

	temp=edges[i].begin;

	edges[i].begin=edges[j].begin;

	edges[j].begin=temp;

	temp=edges[i].end;

	edges[i].end=edges[j].end;

	edges[j].end=temp;

	temp=edges[i].weight;

	edges[i].weight=edges[j].weight;

	edges[j].weight=temp;

}

void sort(Edge edges[],MGraph *G)		/* 对权值进行排序 */

{

	int i,j;

	for ( i=0;i<G->numEdges;i++)

	{

		for ( j=i+1;j<G->numEdges;j++)

		{

			if (edges[i].weight>edges[j].weight)

			{

				Swap(edges,i,j);

			}

		}

	}

	cout<<"权排序之后的为:"<<endl;

	for (i=0;i<G->numEdges;i++)

	{

		cout<<"("<<edges[i].begin<<","<<edges[i].end<<")"<<endl;

	}

}

int Find(int *parent,int f)		/*查找连线顶点的尾部下标*/

{

	while (parent[f]>0)

		f=parent[f];

	return f;

}

void MiniSpanTree_Kruskal(MGraph G)

{

	int i,j,n,m;

	Edge edges[MAXEDGE];

	int parent[MAXVEX];

	/*将邻接数组G转化为边集数组edges并按权由小到大排序*******BEGIN*********/

	int k=0;

	for ( i=0;i<G.numVertexes-1;i++)

	{

		for (j=i+1;j<G.numVertexes;j++)

		{

			if (G.arc[i][j]<INFINITY)

			{

				edges[k].begin=i;

				edges[k].end =j;

				edges[k].weight=G.arc[i][j];

				k++;

			}

		}

	}

	sort(edges, &G);

	/***************END***********************/

	for (i=0;i<G.numVertexes;i++)

		parent[i]=0;	/* 初始化数组值为0 */

	cout<<"Kruskal 算法生成最小生成树，结果为："<<endl;

	for (i=0;i<G.numEdges;i++)	/* 循环每一条边 */

	{

		n=Find(parent,edges[i].begin);

		m=Find(parent,edges[i].end);

		if (n!=m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */

		{

			parent[n]=m;	/* 将此边的结尾顶点放入下标为起点的parent中。 */

							/* 表示此顶点已经在生成树集合中 */

			cout<<"("<<edges[i].begin<<","<<edges[i].end<<") "<<edges[i].weight<<endl;

		}

	}

}

对于如下所示的图：

运行程序，结果如下：

巴特西

C++编程练习(10)----“图的最小生成树“（Prim算法、Kruskal算法）

最新文章

热门文章