Chinaunix首页 | 论坛 | 博客
  • 博客访问: 153204
  • 博文数量: 116
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 20
  • 用 户 组: 普通用户
  • 注册时间: 2017-08-21 15:04
文章分类

全部博文(116)

文章存档

2014年(1)

2013年(13)

2012年(27)

2011年(49)

2010年(26)

分类: C/C++

2013-02-13 23:35:20

    一个连通图的生成树是一个极小的连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。

    找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。下面分别介绍两种算法。

一、普里姆(Prim)算法

    普里姆算法,图论中的一种算法,可在加权连通图里搜索最小生成树。意即此算法搜索到的边子集所构成的树中,不但包括连通图里的所有顶点,且其所有边的权值之和亦为最小。

1.1 算法描述

    从单一顶点开始,普里姆算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。
    (1)输入:一个加权连通图,其中顶点集合为V,边集合为E;
    (2)初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {};
    (3)重复下列操作,直到Vnew = V:
            在集合E中选取权值最小的边(u, v),其中u为集合Vnew中的元素,而v则不是(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
            将v加入集合Vnew中,将(u, v)加入集合Enew中;
    (4)输出:使用集合VnewEnew来描述所得到的最小生成树。

1.2 例示

      

      

1.3 普里姆算法实现

/* 邻接矩阵表示的图结构*/
#include 
#include 
#include 

typedef char VertexType;		//顶点类型应由用户定义
typedef int EdgeType;			//边上的权值类型应由用户定义

#define MAXVEX	100				//最大顶点数,应由用户定义
#define INFINITY	65535		//用65535来代表无穷大
#define DEBUG

//邻接矩阵结构
typedef struct
{
	VertexType vexs[MAXVEX];	//顶点表
	EdgeType   arc[MAXVEX][MAXVEX]; //邻接矩阵,可看作边
	int numVertexes, numEdges;		//图中当前的顶点数和边数
}Graph;

//定位
int locates(Graph *g, char ch)
{
	int i = 0;
	for(i = 0; i < g->numVertexes; i++)
	{
		if(g->vexs[i] == ch)
		{
			break;
		}
	}
	if(i >= g->numVertexes)
	{
		return -1;
	}
	
	return i;
}

//建立一个无向网图的邻接矩阵表示
void CreateGraph(Graph *g)
{
	int i, j, k, w;
	printf("输入顶点数和边数:\n");
	scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
	
	#ifdef DEBUG
	printf("%d %d\n", g->numVertexes, g->numEdges);
	#endif

	for(i = 0; i < g->numVertexes; i++)
	{
		printf("请输入顶点%d:\n", i);
		g->vexs[i] = getchar();
		while(g->vexs[i] == '\n')
		{
			g->vexs[i] = getchar();
		}
	}
	
	#ifdef DEBUG
	for(i = 0; i < g->numVertexes; i++)
	{
		printf("%c ", g->vexs[i]);
	}
	printf("\n");
	#endif


	for(i = 0; i < g->numEdges; i++)
	{
		for(j = 0; j < g->numEdges; j++)
		{
			g->arc[i][j] = INFINITY;	//邻接矩阵初始化
		}
	}
	for(k = 0; k < g->numEdges; k++)
	{
		char p, q;
		printf("输入边(vi,vj)上的下标i,下标j和权值:\n");
		
		p = getchar();
		while(p == '\n')
		{
			p = getchar();
		}
		q = getchar();
		while(q == '\n')
		{
			q = getchar();
		}
		scanf("%d", &w);	
		
		int m = -1;
		int n = -1;
		m = locates(g, p);
		n = locates(g, q);
		if(n == -1 || m == -1)
		{
			fprintf(stderr, "there is no this vertex.\n");
			return;
		}
		//getchar();
		g->arc[m][n] = w;
		g->arc[n][m] = g->arc[m][n];	//因为是无向图,矩阵对称
	}
}

//打印图
void printGraph(Graph g)
{
	int i, j;
	printf("构建的邻接矩阵如下所示.\n");
	for(i = 0; i < g.numVertexes; i++)
	{
		for(j = 0; j < g.numVertexes; j++)
		{
			printf("%5d  ", g.arc[i][j]);
		}
		printf("\n");
	}
}

//prime算法最小生成树
void MiniSpanTree_Prime(Graph g)
{
	int min, i, j, k;
	int adjvex[MAXVEX];			//保存相关顶点下标
	int lowcost[MAXVEX];		//保存相关顶点间边的权值
	lowcost[0] = 0;				//初始化第一个权值为0,即v0加入生成树

	adjvex[0] = 0;				//初始化第一个顶点下标为0
	for(i = 1; i < g.numVertexes; i++)
	{
		//循环除下标为0外的全部顶点
		lowcost[i] = g.arc[0][i];	//将v0顶点与之有边的权值存入数组
		adjvex[i] = 0;				//初始化都为v0下标
	}
	for(i = 1; i < g.numVertexes; i++)
	{
		min = INFINITY;				//初始化最小权值为无穷大
		j = 1;
		k = 0;
		while(j < g.numVertexes)	//循环全部顶点
		{
			//如果权值不为0,且权值小于min
			if(lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];		//则让当前权值成为最小值
				k = j;					//将当前最小值的下标存入k
			}
			j++;
		}
		printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小边
		lowcost[k] = 0;					//将当前顶点的权值设置为0,表示此顶点已经完成任务

		for(j = 1; j < g.numVertexes; j++)//循环所有顶点
		{
			if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j])
			{
				//若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
				lowcost[j] = g.arc[k][j];
				adjvex[j] = k;				//将下标为k的顶点存入adjvex
			}
		}
	}
	printf("\n");
}

int main(int argc, char **argv)
{
	Graph g;
	
	//邻接矩阵创建图
	CreateGraph(&g);
	//打印网图
	printGraph(g);
	//求最小生成树
	MiniSpanTree_Prime(g);

	return 0;
}
     运行结果如下:

    

    

    

    由代码实现可知,邻接矩阵实现的普里姆算法的时间复杂度为O(n2)。


二、克鲁斯卡尔(Kruskal)算法

    普力马算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路,我们也可以直接就以边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已。此时,我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码:

 //对边集数组Edge结构的定义
  typedef struct
   {
       int begin;
       int end;
      int weight;
  }Edge;
     我们可以通过程序将邻接矩阵通过程序转化为边集数组,并且对它们的按权值从小到大排序。如下图所示。

    

    于是克鲁斯卡尔算法代码如下,左侧数字为行号。其中MAXEDGE为边数量的最大值,MAXVEX为顶点个数最大值。具体代码如下所示。

/* 邻接矩阵表示的图结构*/
#include 
#include 


typedef char VertexType;		//顶点类型应由用户定义
typedef int EdgeType;			//边上的权值类型应由用户定义

#define MAXVEX	100				//最大顶点数,应由用户定义
#define INFINITY	65535		//用65535来代表无穷大
#define DEBUG

//邻接矩阵结构
typedef struct
{
	VertexType vexs[MAXVEX];	//顶点表
	EdgeType   arc[MAXVEX][MAXVEX]; //邻接矩阵,可看作边
	int numVertexes, numEdges;		//图中当前的顶点数和边数
}Graph;

//边集数组
#define MAXEDGE   100
typedef struct
{
	int begin;
	int end;
	int weight;
}Edge;



//定位
int locates(Graph *g, char ch)
{
	int i = 0;
	for(i = 0; i < g->numVertexes; i++)
	{
		if(g->vexs[i] == ch)
		{
			break;
		}
	}
	if(i >= g->numVertexes)
	{
		return -1;
	}
	
	return i;
}

//建立一个无向网图的邻接矩阵表示
void CreateGraph(Graph *g)
{
	int i, j, k, w;
	printf("输入顶点数和边数:\n");
	scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
	
	#ifdef DEBUG
	printf("%d %d\n", g->numVertexes, g->numEdges);
	#endif

	for(i = 0; i < g->numVertexes; i++)
	{
		printf("请输入顶点%d:\n", i);
		g->vexs[i] = getchar();
		while(g->vexs[i] == '\n')
		{
			g->vexs[i] = getchar();
		}
	}
	
	#ifdef DEBUG
	for(i = 0; i < g->numVertexes; i++)
	{
		printf("%c ", g->vexs[i]);
	}
	printf("\n");
	#endif


	for(i = 0; i < g->numEdges; i++)
	{
		for(j = 0; j < g->numEdges; j++)
		{
			g->arc[i][j] = INFINITY;	//邻接矩阵初始化
		}
	}
	for(k = 0; k < g->numEdges; k++)
	{
		char p, q;
		printf("输入边(vi,vj)上的下标i,下标j和权值:\n");
		
		p = getchar();
		while(p == '\n')
		{
			p = getchar();
		}
		q = getchar();
		while(q == '\n')
		{
			q = getchar();
		}
		scanf("%d", &w);	
		
		int m = -1;
		int n = -1;
		m = locates(g, p);
		n = locates(g, q);
		if(n == -1 || m == -1)
		{
			fprintf(stderr, "there is no this vertex.\n");
			return;
		}
		//getchar();
		g->arc[m][n] = w;
		g->arc[n][m] = g->arc[m][n];	//因为是无向图,矩阵对称
	}
}

//打印图
void printGraph(Graph g)
{
	int i, j;
	printf("构建的邻接矩阵如下所示.\n");
	for(i = 0; i < g.numVertexes; i++)
	{
		for(j = 0; j < g.numVertexes; j++)
		{
			printf("%5d  ", g.arc[i][j]);
		}
		printf("\n");
	}
}

//prime算法最小生成树
void MiniSpanTree_Prime(Graph g)
{
	int min, i, j, k;
	int adjvex[MAXVEX];			//保存相关顶点下标
	int lowcost[MAXVEX];		//保存相关顶点间边的权值
	lowcost[0] = 0;				//初始化第一个权值为0,即v0加入生成树

	adjvex[0] = 0;				//初始化第一个顶点下标为0
	for(i = 1; i < g.numVertexes; i++)
	{
		//循环除下标为0外的全部顶点
		lowcost[i] = g.arc[0][i];	//将v0顶点与之有边的权值存入数组
		adjvex[i] = 0;				//初始化都为v0下标
	}
	for(i = 1; i < g.numVertexes; i++)
	{
		min = INFINITY;				//初始化最小权值为无穷大
		j = 1;
		k = 0;
		while(j < g.numVertexes)	//循环全部顶点
		{
			//如果权值不为0,且权值小于min
			if(lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];		//则让当前权值成为最小值
				k = j;					//将当前最小值的下标存入k
			}
			j++;
		}
		printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小边
		lowcost[k] = 0;					//将当前顶点的权值设置为0,表示此顶点已经完成任务

		for(j = 1; j < g.numVertexes; j++)//循环所有顶点
		{
			if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j])
			{
				//若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
				lowcost[j] = g.arc[k][j];
				adjvex[j] = k;				//将下标为k的顶点存入adjvex
			}
		}
	}
	printf("\n");
}

//查找连线顶点的尾部
int Find(int *parent, int f)
{
	while(parent[f] > 0)
	{
		f = parent[f];
	}
	return f;
}

//直接插入排序
void InsertSort(Edge edges[], int k)
{
	int i, j;
	Edge ss;
	for(i = 1; i <= k; i++)
	{
		if(edges[i].weight < edges[i - 1].weight)
		{
			ss = edges[i];
			for(j = i - 1; edges[j].weight > ss.weight; j--)
			{
				edges[j + 1] = edges[j];
			}
			edges[j + 1] = ss;
		}
	}
}


//将邻接矩阵转化为边集数组
void Convert(Graph g, Edge edges[])
{
	int i;
	int j;
	int k;
	
	k = 0;
	for(i = 0; i < g.numVertexes; i++)
	{
		for(j = i; j < g.numVertexes; j++)
		{
			if(g.arc[i][j] < 65535)
			{
				edges[k].begin = i;
				edges[k].end = j;
				edges[k].weight = g.arc[i][j];
				k++;
			}
		}
	}
	k--;

#ifdef DEBUG
	printf("k = %d\n", k);
	printf("边集数组排序前,如下所示.\n");	
	printf("edges[]		beign		end		weight\n");
	for(i = 0; i < k; i++)
	{
		printf("%d", i);
		printf("		%d", edges[i].begin);
		printf("		%d", edges[i].end);
		printf("		%d", edges[i].weight);
		printf("\n");
	}
#endif
	
	//下面进行排序
	InsertSort(edges, k);
#ifdef DEBUG
	printf("边集数组排序后,如下所示.\n");
	printf("edges[]		beign		end		weight\n");
	for(i = 0; i < k; i++)
	{
		printf("%d", i);
		printf("		%d", edges[i].begin);
		printf("		%d", edges[i].end);
		printf("		%d", edges[i].weight);
		printf("\n");
	}
#endif
}

//克鲁斯卡尔算法实现
void MiniSpanTree_Kruskal(Graph g)	
{
	int i, n, m;
	Edge edges[MAXEDGE];	//定义边集数组
	int parent[MAXVEX];		//定义一数组用来判断边与边是否形成环
	
	//此处为将邻接矩阵转化为边集数组edges并按权值由小到大排序
	
	Convert(g, edges);
	//
	
	for(i = 0; i < g.numVertexes; i++)
	{
		parent[i] = 0;	//初始化数组值为0
	}

	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中
							//表示此顶点已经在生成树集合中
			printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
		}
	}
	printf("\n");
}

int main(int argc, char **argv)
{
	Graph g;
	
	//邻接矩阵创建图
	CreateGraph(&g);
	
	//打印网图
	printGraph(g);
	
	//普里姆算法求最小生成树
	MiniSpanTree_Prime(g);
	
	//克鲁斯卡尔算法求最小生成树
    MiniSpanTree_Kruskal(g);	
	
	return 0;
}
     以下图为例,进行相应的测试

    

    运行结果如下所示。

    

    

    

    

    

    上述运行过程是这样的:

    (1)输入顶点数、边数;

    (2)输入顶点,和边(依次为起点、终点、权值);

    (3)建立邻接矩阵,用来表示该网图;

    (4)进行普里姆算法进行求最小生成树;

    (5)进行克鲁斯卡尔进行求最小生成树;

            --根据已经建立的邻接矩阵求边集数组;

            --然后进行求最小生成树;    

    

    克鲁斯卡尔算法的Find函数由边数e决定,时间复杂度为O(loge),而外面有一个for循环e次,所以克鲁斯卡尔算法的时间复杂度为O(eloge)。《此处不包括由邻接矩阵转为边集数组

    

    对比两个算法,克鲁斯尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。


    

    暂时弄懂了这两个算法,算是重新复习了一下,以后经常看看,不能再忘记了。



    参考:《大话数据结构》、《维基百科


            

                                                                                      梦醒潇湘love    

                                                                                                     2013-01-29 22:43







阅读(361) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~