【基本概念】

歐拉通路：通過(guò)圖中所有邊一次且僅一次行遍所有頂點(diǎn)的通路

歐拉回路：通過(guò)圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路

歐拉圖：具有歐拉回路的圖

半歐拉圖：具有歐拉通路而無(wú)歐拉回路的圖

奇度點(diǎn)：與點(diǎn)相連的邊的數(shù)目為奇數(shù)的點(diǎn)

偶度點(diǎn)：與點(diǎn)相連的邊的數(shù)目為偶數(shù)的點(diǎn)

【歐拉通路/回路的判定】

1.無(wú)向圖

1）歐拉通路：圖是連通的，圖中只有兩個(gè)奇度點(diǎn)，分別是歐拉通路的兩個(gè)端點(diǎn)

對(duì)于歐拉通路，除起點(diǎn)、終點(diǎn)外，每個(gè)點(diǎn)如果進(jìn)入，顯然一定要出去，因此都是偶點(diǎn)

2）歐拉回路：圖是連通的，點(diǎn)均為偶度點(diǎn)

對(duì)于歐拉回路，每個(gè)點(diǎn)進(jìn)入、出去的次數(shù)相等，因此沒(méi)有奇點(diǎn)

2.有向圖

1）歐拉通路：圖是連通的，除兩頂點(diǎn)外其余點(diǎn)的入度等于出度，且這兩個(gè)頂點(diǎn)中，一個(gè)頂點(diǎn)入度比出度大1（起點(diǎn)），另一個(gè)入度比出度小1（終點(diǎn)）

2）歐拉回路：圖是連通的，圖中所有點(diǎn)的入度等于出度。

3.Fleury 算法

Fleury 算法是用于求無(wú)向圖中歐拉回路的算法，其基本思想如下：

任取圖 G 中一頂點(diǎn) v0，令 P0=v0

假設(shè)沿 Pi=v0e1v1e2...eivi，走到頂點(diǎn) vi，按下面的方法從 E(G)-{e1,e2,...,ei} 中選擇 ei+1:
1）ei+1 與 vi 相關(guān)聯(lián)
2）除非無(wú)別的邊可供選擇，否則 ei+1 不應(yīng)是 Gi=G-{e1,e2,...,ei} 中的橋

當(dāng) 2 不能再進(jìn)行時(shí)，算法停止

可以證明的是，當(dāng)算法停止時(shí)，所得到簡(jiǎn)單回路?Pm=v0e1v1e2...emvm(vm=v0) 為G中的歐拉回路

int n,m; int start;//起點(diǎn) int num;//奇度頂點(diǎn)個(gè)數(shù) int degree[N];//頂點(diǎn)的度 int path[N];//存儲(chǔ)歐拉回路 int cnt;//歐拉回路計(jì)數(shù)器 bool G[N][N]; stack<int> S; void dfs(int x){S.push(x);for(int i=1;i<=n;i++){if(G[x][i]){G[x][i]=false;G[i][x]=false;dfs(i);break;}} } void Fleury(int x){S.push(x);while(!S.empty()){bool flag=false;for(int i=1;i<=n;i++){if(G[S.top()][i]==true){ //與起點(diǎn)有關(guān)聯(lián)的邊f(xié)lag=true;break;}}if(flag==true){ //如果有關(guān)聯(lián)的邊int temp=S.top();S.pop();dfs(temp);}else{ //如果沒(méi)有有關(guān)聯(lián)的邊path[cnt++]=S.top();S.pop();}} } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[x][y]=1;G[y][x]=1;degree[x]++;degree[y]++;}cnt=1;num=0;start=1;for(int i=1;i<=n;i++){if(degree[i]&1){//如果某點(diǎn)的度是奇數(shù)if(num==0)//記錄起點(diǎn)start=i;num++;//奇度點(diǎn)個(gè)數(shù)+1}}if(num==0||num==2){//如果存在奇度頂點(diǎn)，則從奇度頂點(diǎn)出發(fā)，否則從頂點(diǎn)0出發(fā)Fleury(start);for(int i=cnt-1;i>=1;i--)printf("%d ",path[i]);printf("\n");}elseprintf("No Euler path.\n");return 0; }

4.并查集判斷無(wú)向圖中是否存在歐拉回路

當(dāng)給出一個(gè)無(wú)向圖時(shí)，若要求判斷圖中是否存在歐拉回路，可以使用并查集判斷圖是否連通，并統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的度數(shù)，依次來(lái)判斷是否存在。

若圖連通且所有點(diǎn)的度數(shù)為偶數(shù)，則說(shuō)明該無(wú)向圖中存在歐拉回路。

#include<iostream> #include<cstdio> #include<cstring> #define N 1001 using namespace std; int n,m; int degree[N]; int father[N]; int Find(int x){if(father[x]==-1)return x;return father[x]=Find(father[x]); } void Union(int x,int y){x=Find(x);y=Find(y);if(x!=y)father[x]=y; } int main(){while(scanf("%d%d",&n,&m)!=EOF){memset(degree,0,sizeof(degree));memset(father,-1,sizeof(father));for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);degree[x]++;degree[y]++;Union(x,y);}int cnt=0;//記錄連通分量for(int i=1;i<=n;i++)if(Find(i)==i)cnt++;if(cnt!=1)//若cnt大于1，說(shuō)明圖不連通printf("NO\n");else{int num=0;//統(tǒng)計(jì)度數(shù)為奇數(shù)的點(diǎn)for(int i=1;i<=n;i++)if(degree[i]&1)num++;if(num==0)printf("YES\n");elseprintf("NO\n");}}return 0; }

【應(yīng)用】

對(duì)于一般的單詞首尾相連的問(wèn)題，通常都是轉(zhuǎn)化為有向圖的歐拉通路問(wèn)題。

例如：給出多個(gè)單詞，問(wèn)能不能將所有單詞組成一個(gè)序列，序列的前一個(gè)單詞的尾字母與后一個(gè)單詞的頭字母相同

如果把每個(gè)單詞看出無(wú)向的邊，那么最終求出的歐拉通路可能存在兩個(gè)單詞尾部和尾部相連的情況。

1.無(wú)向歐拉圖打印歐拉通路/回路

輸入保證一個(gè)有?n 個(gè)點(diǎn)，m 條邊的具有歐拉回路或歐拉路徑的無(wú)向圖，要求打印出圖的歐拉回路或通路。

如果要打印歐拉通路，輸入的 start 一定要是起點(diǎn)之一，即：，否則只是亂序打印圖中所有的邊。

#include<iostream> #include<cstdio> #include<algorithm> #include<stack> #define N 1001 using namespace std; int n,m; int G[N][N]; bool vis[N][N];//vis[i][j]=1表示點(diǎn)i到j(luò)之間存在一條邊 void euler(int x){//打印以x為起點(diǎn)的歐拉回路或通路for(int y=1;y<=n;y++){if(vis[x][y]||vis[y][x]){vis[x][y]=0;//去掉x-y這條邊vis[y][x]=0;//去掉y-x這條邊euler(y);//首尾相連逆序打印歐拉通路//printf("%d %d\n",x,y);}}//逆序打印歐拉回路printf("%d ",x); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[x][y]=1;G[y][x]=1;vis[x][y]=1;vis[y][x]=1;}int start;scanf("%d",&start);euler(start);//打印以x為起點(diǎn)的歐拉回路或通路return 0; }

2.有向歐拉圖打印歐拉通路/回路

輸入保證是一?n 個(gè)點(diǎn)，m 條邊的具有歐拉回路或歐拉路徑的有向圖，要求打印出圖的歐拉回路或通路。

如果要打印歐拉通路，那么輸入的 start 一定要是起點(diǎn)之一，即：，否則只是亂序打印圖中所有的邊。

1）鄰接矩陣實(shí)現(xiàn)

#include<iostream> #include<cstdio> #include<algorithm> #include<stack> #define N 1001 using namespace std; int n,m; int G[N][N]; bool vis[N][N];//vis[i][j]=1表示點(diǎn)i到j(luò)之間存在一條邊 void euler(int x){//打印以x為起點(diǎn)的歐拉回路或通路for(int y=1;y<=n;y++){if(vis[x][y]){vis[x][y]=0;//去掉x-y這條邊euler(y);//首尾相連逆序打印歐拉通路//printf("%d %d\n",x,y);}}//逆序打印歐拉回路printf("%d ",x); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[x][y]=1;vis[x][y]=1;}int start;scanf("%d",&start);euler(start);//打印以x為起點(diǎn)的歐拉回路或通路return 0; }

2）鄰接鏈表實(shí)現(xiàn)

struct Edge{int endd;bool vis;Edge(int endd,bool vis):endd(endd),vis(vis){} }; int n,m; vector<Edge> G[N]; void euler(int x) {for(int i=G[x].size()-1; i>=0;i--) {if (!G[x][i].vis){G[x][i].vis = 1;euler(G[x][i].endd);}}printf("%d\n",x); }int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(Edge(y,false));G[y].push_back(Edge(x,false));}int start=1;euler(start);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的图论 —— 图的遍历 —— 欧拉通路与欧拉回路问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。