图论--寻找欧拉回路

首先介绍一下fleury算法。

大概描述是这样子的：

（1）设图G的顶点集为V(G)， 从中任取一个顶点V0，令P0 = V0;

（2）设Pi=v0e1v1e2...eivi已经行遍，按下面的方面来从E(G)-{e1, e2, ..., ei}中选取ei+1:

    （2.1）ei+1与vi相关联，也就是，从vi射出。

    （2.2）除非无别的边可供选择，否则ei+1不应该为Gi=G-{e1, e2, ..., ei}中的桥。所谓的桥，是指当把它从图中删除时，原本连通的图不连通了。

（3）当（2）不能再进行时，算法停止。

 

算法的思想我是理解的，不过我也没有实现。在网上看到一个用递归实现的算法，很简洁，可是我不确定它是否是fleury算法，因为我没有看到有关边的选择是如何优先避开桥的。先贴这里吧。

 

void dfs( int** g, int vnum, int id, int* s, int* front ){
	int i;
	s[++(*front)] = id;
	for( i=0; i<vnum; i++ ){
		if( g[i][id]>0 ){
			g[i][id] --;
			g[id][i] --;
			dfs(g, vnum, i, s, front);
			break;
		}
	}
}
		
void eulerPath( int** g, int vnum, int x ){
	int* stack = (int*)malloc( sizeof(int)*vnum );
	int front = 0;
	stack[front] = x;
	int i, b;
	while( front>=0 ){
		b = 0;
		for( i=0; i<vnum; i++ ){
			if( g[stack[front]][i] > 0 ){
				b = 1;
				break;
			}
		}
		if( b == 0 ){
			printf( "%d ", stack[front] );
			front -- ;
		}else{
			front--;
			dfs( g, vnum, stack[front+1],stack, &front );
		}
	}
	printf( "end of eulerPath\n" );
	free( stack );
}

 递归得很厉害。我又想不大明白。于是就自己照着书本的那个证明，做了如下的画圈圈的算法。

 

typedef struct node{
	int id;
	struct node* next;
	struct node* prev;
}pathNode;

typedef struct {
	struct node* head;
	struct node* current;
}path;

//this function finds the euler route and return its head
path* eulerCircle( int** g, int* indgr, int num ){
	path* p = (path*)malloc( sizeof(path) );
	p->head = (pathNode*)malloc( sizeof( pathNode ) );
	(p->head)->id = 0;
	(p->head)->prev = NULL;
	(p->head)->next = NULL;
	//without lose of generality, we start our search from v0
	p->current = p->head;
	int i;
	int count=0, top=0;
	while( count < num ){
		path* ptmp = (path*)malloc( sizeof(path) );
		ptmp->head = (pathNode*)malloc( sizeof( pathNode ) );
		ptmp->head->id = -1;
		ptmp->head->prev = NULL;
		ptmp->head->next = NULL;
		ptmp->current = ptmp->head;
		int c=top;
		//this while loop is to find a loop in the graph
		while(1){
			for( i=0; i<num; i++ ){
				if( g[c][i] > 0 ){
					g[c][i]--;
					g[i][c]--;
					indgr[c]--;
					indgr[i]--;
					if( indgr[c] == 0 )
						count++;
					if( indgr[i] == 0 )
						count++;
					c = i;
					ptmp->current->id = i;
					pathNode* t = (pathNode*)malloc( sizeof(pathNode) );
					t->id = -1;
					t->next = NULL;
					ptmp->current->next = t;
					t->prev = ptmp->current;
					ptmp->current = t;
					break;
				}
			}
			if( c == top )
				break;
		}
		pathNode* t = ptmp->current;
		pathNode* tt = p->current->next;
		//find a new circle from vertex top
		if( t->prev != NULL ){
			ptmp->current = ptmp->current->prev;
			ptmp->current->next = NULL;
			free( t );
			p->current->next = ptmp->head;
			ptmp->head->prev = p->current;
			p->current = ptmp->current;
			p->current->next = tt;
			if( tt != NULL )
				tt->prev = p->current;
		}else{
			free( t );
			free( ptmp );
		}
		//modify the value of top, to start a new circle
		tt = p->current;
		while( tt != NULL ){
			if( indgr[tt->id] > 0 ){
				top=tt->id;
				p->current = tt;
				break;
			}
			tt = tt->prev;
		}

	}
	return p;
}

//this function prints the path we've just found
void printPath( path* p ){
	if( p == NULL ){
		printf( "NULL pointer\n" );
		return ;
	}
	pathNode* head = p->head;
	pathNode* t = head;
	for( t=head; t!=NULL; t=t->next )
		printf( "%d->", t->id );
	printf( "\n" );
}

//this function frees the path we constructed in eulerCircle
void freePath( path* p ){
	if( p == NULL ){
		printf( "NULL pointer\n" );
		return ;
	}
	
	pathNode* head = p->head;
	pathNode* t = head;
	while( head != NULL ){
		t = head->next;
		free(head);
		head = t;
	}
}

 

大概思想是这样子的：首先找到一个圈，将圈上的边去掉，此时图中顶点的入度依然为偶数（或者为0），从刚才的圈中任找一个入度不为0的顶点（肯定至少存在一个，不然图就是不连通的了），再找一个圈，也就是说，像原先0->1->2->0的圈，假如从2出发有2->5->6->4->2的圈，那么现在就可以形成一个0->1->2->5->6->4->2->0的圈了。所以其实结果我的主要任务就变成维护好这个列表了，呵呵。。。如果用高级一点的数据结构的话，是不需要多少代码的。。哈哈。这个算法就是我用在中国邮递员里面的算法。

 

我还是希望有个人能跟我讲讲上面那个递归的算法。。也或许是我对深搜还没有真正透彻的理解吧。