歐拉圖性質：

1.無向連通圖G是歐拉圖，當且僅當G不含奇數(shù)度結點(G的所有結點度數(shù)為偶數(shù))；

2.無向連通圖G含有歐拉通路，當且僅當G有零個或兩個奇數(shù)度的結點；

3.有向連通圖D是歐拉圖，當且僅當該圖為連通圖且D中每個結點的入度=出度；

4.有向連通圖D含有歐拉通路，當且僅當該圖為連通圖且D中除兩個結點外，其余每個結點的入度=出度，且此兩點滿足deg－(u)－deg+(v)=±1。（起始點s的入度=出度-1，結束點t的出度=入度-1 或兩個點的入度=出度）；

?

對于歐拉圖問題，有如下解決問題的方法：

1.Eular算法（歐拉算法），歐拉問題最標準的算法。

2.Fluery算法（佛羅萊算法），歐拉問題最廣泛的算法

3.Hierholzer (希霍爾澤算法應該是這么翻譯）又叫逐步插入回路法，高效的算法。

4.DFS算法，暴力無腦解題算法，雖然Fluery，Euler也是遞歸實現(xiàn)。這個我看看又看了看，確實跟Euler沒區(qū)別，跟Hierholzer也沒區(qū)別

5.并查集算法，網(wǎng)絡流解混合圖的時候可以使用。https://blog.csdn.net/liyanfeng1996/article/details/52767039

以上是網(wǎng)上的各種說法的總結，也就是只有這3種做法，暴力的搜索（1，3，4）

?

1.對于第一種方法只要有歐拉路徑或者歐拉回路，就可以使用，應該是可以用于無向圖的，不過使用前需要判斷節(jié)點的度，是否存在，復雜度有點高，也不用避免隔什么的感覺跟DFS很像，簡單的題暴力就完事了。

?

?

?就是暴力，能走就走，不能走就不走，然后從小號到最大號遍歷，也就保證了路徑的序號為字典序最小的情況。

模板：

int g[510][510]; stack<int> s; int d[510]; void euler(int u) {for(int v=1; v<=500; v++){if(g[u][v]){g[u][v]--;g[v][u]--;euler(v);s.push(v);}} } int main() {int u,v;int n;cin>>n>>m;// 點，邊f(xié)or(int i=1; i<=m; i++){cin>>u>>v;g[u][v]++;g[v][u]++;d[u]++;d[v]++;}int flag=1;int cnt=0;for(int i=n; i>=1; i--)if(d[i]%2) {flag=i;cnt++;}if(cnt>2){cout<<"No Euler"<<endl;return 0;}euler(flag);s.push(flag);while(!s.empty()){cout<<s.top()<<endl;s.pop();} } void fleury(int s){bool flag;st.push(s);while(!st.empty()){flag = 0;for(int i = 1; i <= n; i++){if(edge[st.top()][i] > 0){flag = 1; break;}}if(flag){int x = st.top();st.pop();dfs(x);}else{printf("%d ",st.top());st.pop();}}

?

總結

以上是生活随笔為你收集整理的图论-欧拉图-欧拉回路-Euler-Fluery-Hierholzer-逐步插入回路法-DFS详解-并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

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