首页 > 代码库 > 欧拉回路&Fleury算法&实现
欧拉回路&Fleury算法&实现
基本知识
欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次,
称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。
判断欧拉路是否存在的方法
有向图:图连通,有一个顶点出度大入度1,有一个顶点入度大出度1,其余都是出度=入度。
无向图:图连通,只有两个顶点是奇数度,其余都是偶数度的。
判断欧拉回路是否存在的方法
有向图:图连通,所有的顶点出度=入度。
无向图:图连通,所有顶点都是偶数度。
程序实现一般是如下过程:
1.利用并查集判断图是否连通,即判断p[i] < 0的个数,如果大于1,说明不连通。
2.根据出度入度个数,判断是否满足要求。
3.利用dfs输出路径。
考虑一个比较有意思的问题,单词连接问题。
样例
考虑一个比较有意思的问题,单词连接问题。
给出n个单词,如果一个单词的尾和另一个单词的头字符相等,那么可以相连,问这n个单词是否可以排成一列。
这个显然可以使用欧拉路问题进行解决。考虑每一个单词的第一个字母入度加1,每一个单词的最后一个字母出度加1,然后每一个单词都相当于一条有向边,这样就可以利用这些信息进行是否联通的判断,比较高效的策略是使用并查集进行判断。
实现代码如下:
#include <iostream> #include <assert.h> #include <string> using namespace std; const int maxv = 27; int in[maxv]; int out[maxv]; int p[maxv]; int rankk[maxv]; int used[maxv]; void init() { for(int i=0;i<maxv;i++) { p[i] = i; in[i] = 0; out[i]=0; rankk[i] =1; } } int find(int a) { if(p[a]==a) return p[a]; p[a] = find(p[a]); return p[a]; } bool unions(int a,int b) { int pa = find(a),pb = find(b); if(pa==pb) return false; if(rankk[pa]>rankk[pb]) { p[pb]=pa; rankk[pa]+=rankk[pb]; } else { p[pa] = pb; rankk[pb]+=rankk[pa]; } return true; } int main(int argc,char* argv[]) { init(); int wordCount = 0; cin>>wordCount; string word; while(wordCount>0) { cin>>word; int len = word.size(); in[word[0]-'a']++; out[word[len-1]-'a']++; used[word[0]-'a'] = 1; used[word[len-1]-'a'] = 1; unions(word[0]-'a',word[len-1]-'a'); wordCount--; } int scc = 0; for(int i=0;i<maxv;i++) { if(used[i]&&p[i]==i) { scc++; //break; } } cout<<scc<<endl; assert(scc<=1); if(scc>1) { cout<<"scc is greater than 1 so it is not ok exit"<<endl; return -1; } int a=0,b=0; for(int i=0;i<maxv;i++) { if(!used[i]) continue; cout<<'a'+i<<" "<<in[i]<<" "<<out[i]<<endl; if(in[i]==out[i]) continue; if(in[i]-out[i]==1) a++; else if(in[i]-out[i]==-1) b++; else { cout<<"not ok,exit"<<endl; return -1; } } if((a==1&&b==1)||a+b==0) cout<<"OK"<<endl; return 0; }
Fleury算法
对于有向图和无向图都可以使用Fleury算法累实现寻找欧拉回路问题。下面介绍一下Fleury算法的思路。
Fleury算法:
任取v0∈V(G),令P0=v0;
设Pi=v0e1v1e2…ei vi已经行遍,按下面方法从中选取ei+1:
(a)ei+1与vi相关联;
(b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2, …, ei}中的桥(所谓桥是一条删除后使连通图不再连通的边);
(c)当(b)不能再进行时,算法停止。
可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2….emvm(vm=v0)为G中的一条欧拉回路,复杂度为O(e*e)。
// // Eular.h // HelloWorld // // Created by jackqiu on 15-1-5. // Copyright (c) 2015年 jackqiu. All rights reserved. // #ifndef HelloWorld_Eular_h #define HelloWorld_Eular_h class Eular { private: #define SIZE 1000 int graph[SIZE][SIZE]; int stack[SIZE+10]; int top;//the int size; /** Fleury算法: 任取v0∈V(G),令P0=v0; 设Pi=v0e1v1e2…ei vi已经行遍,按下面方法从中选取ei+1: (a)ei+1与vi相关联; (b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2, …, ei}中的桥(所谓桥是一条删除后使连通图不再连通的边); (c)当(b)不能再进行时,算法停止。 可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2….emvm(vm=v0)为G中的一条欧拉回路,复杂度为O(e*e)。 */ void DFS(int x,int t) { stack[++top] = x; int brige = 0,i; for(i=t;i<size;i++) { if(graph[x][i]) { graph[x][i] = graph[i][x] = 0; brige = 1; DFS(i,0); break; } } if(brige==0)//没有边的话就往后退 { int beforeX = stack[--top];//相当于先pop,然后取栈顶的元素 graph[beforeX][x] = graph[x][beforeX] = 1;//回复刚刚的数据,返回的上一个节点 if(top== size) { stack[++top] = x; } else { top--; DFS(beforeX,x+1);//visit the next node of x } } } public: Eular() { } void eular() { cout<<"please input the size:"; cin>>size; cout<<"input the edge for example 1 2 (-1 -1) to exit"<<endl; int a,b; cin>>a>>b; graph[a][b] = graph[b][a] = 1; while(a!=-1&&b!=-1) { cin>>a>>b; graph[a][b] = graph[b][a] = 1; } top = 0; DFS(0,0); for(;top>0;top--) { cout<<stack[top]<<" "; } cout<<endl; } }; #endif
欧拉回路&Fleury算法&实现