生活随笔
收集整理的這篇文章主要介紹了
欧拉回路与欧拉道路
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
? ? ??
圖G的一個回路，若它恰通過G中每條邊一次,則稱該回路為歐拉(Euler)回路。
如果一個圖只是形成一個連通所有節(jié)點的鏈，且每一點只走一次，則成為歐拉道路。
具有歐拉回路或歐拉道路的圖稱為歐拉圖（簡稱E圖）。
有向圖的歐拉回路
一個有向圖存在歐拉回路的前提條件是這個圖是個連通圖，其次要求其每個點的入度等于出度，或者其中有一個點的出度比入度大1，另一個點的入度比出度大一這樣就存在一條歐拉回路。
如果其每個點的入度等于出度則從任意一點出發(fā)，可以走出一條歐拉回路，如果是第二種情況，則必須從出度大于入度 1 的點出發(fā)到入度大于出度 1 的點結(jié)束，走出一條歐拉道路。
無向圖的歐拉回路
跟有向圖一樣，首先必須連通，其次如果最多只有兩個奇點。則滿足歐拉回路或歐拉道路，有奇點就從任意一個奇點出發(fā)找科形成一條歐拉道路，否則從任意一點出發(fā)都能找出歐拉回路。（注意：百度百科上是錯的）
如果只是判斷一個圖是否能夠形成歐拉回路的話，就用上面的思路：
首先根據(jù)出度跟入度的關(guān)系，判斷是否滿足要求
然后用判斷圖的連通性可以用并查集或者Dfs如果要求路徑的話可以用Dfs
要是需要求出歐拉路徑，就用下面這個函數(shù)。
下面這個程序，是通過遍歷一個圖來求其歐拉回路或歐拉道路的。如果需要打印歐拉道路，在主程序中調(diào)用，參數(shù)必須是道路的起點，另外說明的是，這樣打印出來是逆序的，因此在使用的時候，應(yīng)該用棧壓入棧中，還有就是其對無向圖和有向圖遍歷都有用。其實這個算法跟最小生成樹prim里面每次求連接上一邊最小權(quán)值的邊算法一樣，這個只是那個算法的一個簡化。可根據(jù)那個進行理解。
[cpp]?view plaincopyprint?
void?euler(int?u)?? {?? ????for(int?v=0;v<n;v++)?? ????{?? ????????if(map[u][v]?&&?!vis[u][v])?? ????????{?? ????????????vis[u][v]?=?vis[v][u]?=?1;?? ????????????euler(v);?? ????????????printf("%d?%d\n",u,v);?? ????????}?? ????}?? }??
uva10054 - The Necklace
這個題題意很容易理解，一個鏈子斷了，鏈子上的珠子兩邊分別有兩個值，要把所有珠子鏈起來的話任意兩個相鄰的珠子的值必須相等才行，另外要說的是第二組數(shù)據(jù)是一組很好的數(shù)據(jù)。可根據(jù)其推出是用無向圖，首先判斷是否滿足每個點都是偶點（因為是回路，不是道路）。然后利用上面歐拉代碼遍歷輸出即可。
[cpp]?view plaincopyprint?
#include?<cstdio>?? #include?<cstring>?? #include?<stack>?? #define?Max?60?? using?namespace?std;?? int?map[Max][Max];?? int?in[Max];?? struct?E{?int?u,?v;?}?tmp;?? stack?<E>?st;?? ?? void?euler(?int?u?)?? {?? ????for?(?int?v?=?1;?v?<?n;?++v?)?if?(?map[u][v]?)?? ????{?? ????????map[u][v]--;?map[v][u]?=?map[u][v];?? ????????euler(?v?);?? ????????tmp.u?=?u,?tmp.v?=?v;?? ????????st.push(tmp);?? ????}?? }?? int?main()?? {?? ????int?n,T,a,b;?? ????scanf("%d",&T);?? ????for(int?cas=1;cas<=T;cas++)?? ????{?? ????????scanf("%d",&n);?? ????????memset(map,0,sizeof(map));?? ????????memset(in,0,sizeof(in));?? ?????????? ????????for(int?i=0;i<n;i++)?? ????????{?? ????????????scanf("%d%d",&a,&b);?? ????????????++in[a];++in[b];?? ????????????++map[a][b];?? ????????????map[b][a]=map[a][b];?? ????????}?? ????????bool?ok=true;?? ????????for(int?i=0;i<=50;i++)?? ????????{?? ????????????if(in[i]%2)?? ????????????????ok=false;?? ????????}?? ????????printf("Case?#%d\n",cas);?? ????????if(!ok)?? ????????printf("some?beads?may?be?lost\n");?? ????????else?? ????????{?? ????????????euler(a);?? ????????????while?(?!st.empty()?)?{?? ????????????????tmp?=?st.top();?st.pop();?? ????????????????printf("%d?%d\n",?tmp.u,?tmp.v);?? ????????????}?? ????????}?? ????????printf("\n");?? ????}?? ????return?0;?? }??
UVA10129 - Play on Words?這道題題意是給出n個單詞，讓每個點此的首字母指向未字母形成連通，這樣形成一個有向圖，求這個有向圖的歐拉回路。
思想就是：首先讀入圖，然后根據(jù)出度和入度判斷是否滿足，單手Dfs判斷連通性。
[cpp]?view plaincopyprint?
#include<stdio.h>?? #include<string.h>?? #include<math.h>?? int?visit[26],a[26][26];?? void?dfs(int?x)?? {?? ????int?i;?? ????visit[x]=0;?? ????for?(i=0;i<26;i++)?? ????if?((visit[i]==1)&&(a[x][i]==1))?dfs(i);?? }?? int?main()?? {?? ????int?f,t,k1,k2,num,n,i,j,l,in[26],out[26];?? ????char?s[1010];?? ????scanf("%d",&t);?? ????while?(t--)?? ????{?? ????????memset(a,0,sizeof(a));?? ????????for?(i=0;i<26;i++)?? ????????{in[i]=0;?out[i]=0;?visit[i]=0;}?? ????????scanf("%d\n",&n);?? ????????while?(n--)?? ????????{?? ????????????gets(s);?l=strlen(s);?? ????????????k1=s[0]-'a';?k2=s[l-1]-'a';?? ????????????++in[k1];?++out[k2];?? ????????????visit[k1]=1;?visit[k2]=1;?? ????????????a[k1][k2]=1;?? ????????????num=k1;?? ????????}?? ????????for?(i=0;i<26;i++)?? ????????in[i]=in[i]-out[i];?? ????????f=0;?k1=0;?k2=0;?? ????????for?(i=0;i<26;i++)?? ????????{?? ????????????if?(in[i]==-1)?++k1;?? ????????????else?if?(in[i]==1)??{++k2;num=i;}??? ????????????else?if?(in[i]!=0)??f=1;?? ????????}?? ?? ????????if?(f==0)?? ????????{?? ????????????if?((k1+k2==0)?||?((k1==1)&&(k2==1)))?? ????????????{?? ????????????????dfs(num);?? ????????????????for?(i=0;i<26;i++)?? ????????????????f+=visit[i];?? ????????????}?? ????????????else?f=1;?? ????????}?? ????????if?(f!=0)?printf("The?door?cannot?be?opened.\n");?? ???????else?printf("Ordering?is?possible.\n");?? ?? ????}?? ????return?0;?? }???
總結(jié)
以上是生活随笔為你收集整理的欧拉回路与欧拉道路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
