图论--寻找欧拉回路
首先介绍一下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 headpath* 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 v0p->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 graphwhile(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 topif( 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 circlett = 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 foundvoid 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 eulerCirclevoid 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的圈了。所以其实结果我的主要任务就变成维护好这个列表了，呵呵。。。如果用高级一点的数据结构的话，是不需要多少代码的。。哈哈。这个算法就是我用在中国邮递员里面的算法。
?
我还是希望有个人能跟我讲讲上面那个递归的算法。。也或许是我对深搜还没有真正透彻的理解吧。