图论--中国邮递员问题

中国邮递员问题就比较悲催了。前后花了我大概有三天的时间。。今天才做完的。。

 

首先描述一下问题：

邮递员从邮局出发送信，要求对辖区内每条街都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线？

如果街区形成的图本身就是一个欧拉回路，最短路自然是所有街道的总长度。可是如果不是，我们将必须重复一些路径，换句话说，怎样使重复的路径的总长度最短。

 

这个问题涉及的问题包括：

（1）判别是否是欧拉回路（首先图必须是连通的，其次所有顶点的度数都为偶数。）

（2）如果不是欧拉回路，即有多个顶点的度数为奇数（我们且称它们为奇点吧，奇点的个数必定是偶数），则我们必须将该图构造成一个欧拉图，需要做的事情有：

  （2.1）计算各个奇点间的最短路径

  （2.2）将这些奇点以及奇点间的最短路径做为一个二分图，求二分图的最小权匹配。（例如，我们有四个奇点1,2,3,4, 则左1与右1之间的边的权重为无穷大，左1与右2的边的权重为奇点1到奇点2的最短距离，依此类推，最终得到的最小权总数是实际增加的路径长度的两倍）

  （2.3）最小权匹配得到的两两成对的顶点，将这些顶点之间的最短路径经过的边重复一遍，形成的欧拉回路将是最短的。

（3）找出一条欧拉回路。在网上看到有两种找法，一种是fleury算法，一种是我自己命名的画圈圈的方法，也就是用来证明“所有顶点的度数都为偶数的连通图必定是欧拉回路”的方法。

 

因此，整个过程涉及到的算法包括：

（1）最短路径算法。（这个我想大家都懂，不必多说了）

（2）KM算法求二分图最小权匹配。（http://www.cnblogs.com/zhuangli/archive/2008/08/03/1259248.html 我主要也是参考这个的）

（3）fleury算法或“画圈圈”算法。

 

具体实现的时候，我用两个矩阵来记录这个图，一个是点与点间的距离，一个是点与点间边的数目（一开始最多是一条），同时记录总路径长度。然后也用了两个数组来记录奇点，一个是作索引用的。把所有奇点做为起始点求最短路径。我在最短路径中把求到的最短距离记录到了二分图的权重矩阵中，并返回了记录路径的数组。然后把在最短路径中求出来的权重矩阵做为最小权匹配的输入，求出最优匹配。最后通过索引数组和在求最短路径时得到的路径(s)一一添加到记录点与点间边数的矩阵中，然后将它作为求欧拉回路的输入。

 

主函数如下：

int connected( int** g, int vnum );
int* bestMatch( int** weight, int n );
path* eulerCircle( int** g, int* indgr, int num );
main(){
	
	int vnum, onum, i, j, k, total=0, hasEuler=1;
	//ge is to record the number of edges between to nodes while gd the distance
	int** ge, **gd;
	int* indgr;
	int** weight;
	printf( "enter the number of nodes: " );
	scanf( "%d", &vnum );
	ge = (int**)malloc( sizeof(int*)*vnum );
	gd = (int**)malloc( sizeof(int*)*vnum );
	for( i=0; i<vnum; i++ ){
		ge[i] = (int*)malloc( sizeof(int)*vnum );
		memset( ge[i], 0, sizeof(int)*vnum );
		gd[i] = (int*)malloc( sizeof(int)*vnum );
	}
	for( i=0; i<vnum; i++ )
		for( j=0; j<vnum; j++ )
			gd[i][j] = MXLEN;
	indgr = (int*)malloc( sizeof(int)*vnum );
	memset( indgr, 0, sizeof(int)*vnum );
	printf( "enter the lines and distance in the following format:\n" );
	printf( "startNode endNode distance (stop with -1)\n" );
	scanf( "%d", &i );
	while( i!=-1 ){
		scanf( "%d %d", &j, &k );
		ge[i][j]=1;
		ge[j][i]=1;
		gd[i][j]=k;
		gd[j][i]=k;
		total += k;
		indgr[i]++;
		indgr[j]++;
		scanf( "%d", &i );
	}//thus construct the matrices for our need
	
	//check connectivity
	if( !connected( ge, vnum ) ){
		printf( "the graph is not connected, no route could be found\n" );
		return ;
	}
	
	//check if there is an euler circle already
	for( i=0; i<vnum; i++ ){
		if( indgr[i] & 0x00000001 ){
			hasEuler = 0;
			break;
		}
	}
	
	//construct the graph to a euler path
	if( !hasEuler ){
		//first of all, find out the nodes that have odd degree
		onum = 0;
		j = 0;
		int* oddSet = (int*)malloc( sizeof(int)*vnum );
		memset( oddSet, -1, sizeof(int)*vnum );
		for( i=0; i<vnum; i++ ){
			if( indgr[i]& 0x00000001 ){
				onum++;
				oddSet[i] = j;
				j++;
			}
		}
		int* index = (int*)malloc( sizeof(int)*onum );
		//the paths are used to record the shortest path from nodes to nodes
		//it will be initialized by shortestPath
		int** paths = (int**)malloc( sizeof(int*)*onum );
		weight = (int**)malloc( sizeof(int*)*onum );
		for( i=0; i<onum; i++ ){
			weight[i] = (int*)malloc( sizeof(int)*onum );
			for( j=0; j<onum; j++ )
				weight[i][j] = MXLEN;
		}
		j=0;
		for( i=0; i<vnum; i++ ){
			if( oddSet[i]>=0 ){
				index[j]=i;
				paths[j] = (int*)malloc( sizeof(int)*vnum );
				//in the shortestPath we also construct the weight map of the oddSet
				shortestPath( gd, paths[j], vnum ,i, weight, oddSet ); 
				j++;
			}
		}
		
		//now is to find the best Match for the oddset
		int* result = bestMatch( weight, onum );
		for( i=0; i<onum; i++ ){  //reconstruct the shortestPath from paths[i]
			if( result[i] != -1 ){
				result[result[i]] = -1;
				int tmp1 = index[result[i]];
				int tmp = paths[i][tmp1];
				while( tmp!=index[i] ){
					ge[tmp1][tmp]++;
					ge[tmp][tmp1]++;
					indgr[tmp1]++;
					indgr[tmp]++;
					total += gd[tmp1][tmp];
					tmp1 = tmp;
					tmp = paths[i][tmp];
				}
				ge[tmp1][tmp]++;
				ge[tmp][tmp1]++;
				indgr[tmp1]++;
				indgr[tmp]++;
				total += gd[tmp1][tmp];
			}
		}
		
	}
	path* euler = eulerCircle( ge, indgr, vnum );
	printf( "total distance is %d\n", total );
	printPath( euler );
	freePath( euler );
}

 

connected()很简单，就是一个宽搜，确定整个图是连通的就好。

shortestPath()带了参数paths，weight, oddSet都是为了求最优匹配和重建路径而设的。paths记录的是最短路径中从起始点到目标点前的最后一个顶点，利用这个数组我们可以重建最短路径。

bestMatch()求最小权匹配，返回一个数组，记录匹配的结果。（算法原理可以看一下我上面提供的链接）

eulerCircle()从0开始，通过画圈圈的方法把欧拉回路给找出来。

最后一个函数我另开一篇记录吧，呵呵。