文章目錄

• • 一：什么是歐拉回路？
  • 二： 無向圖中歐拉回路存在的條件
  • 三：如何得到歐拉回路
  • 四：Java實現

一：什么是歐拉回路？

不知道你有沒有玩過這樣一種叫“一筆畫”，從某一點開始畫一個圖形或圖案，期間筆不能從紙上離開而且每條邊只能畫一次。

下面有三個例子，你可以先試一試看看能不能“一筆畫”

第一個圖其實是根本畫不出來的，第二個圖可以畫出，但是不存在起點和終點為同一點的情況，第三個圖可以輕松畫出，而且存在起點和終點為同一點的情況

歐拉回路問題：
如果圖G中的一個路徑包括每個邊恰好一次，則該路徑稱為歐拉路徑(Euler path)。
如果一個回路是歐拉路徑，則稱為歐拉回路(Euler circuit)。
具有歐拉回路的圖稱為歐拉圖（簡稱E圖）。具有歐拉路徑但不具有歐拉回路的圖稱為半歐拉圖。

二： 無向圖中歐拉回路存在的條件

什么情況下才存在歐拉回路呢？
充要條件：當且僅當圖是連通的而且每個頂點的度是偶數
想想一下，如果一個節點v的度為1，那么進入v后只能留在v中，不可能再出來。

但是當有兩個度為奇數的節點分別作為起點和終點，歐拉路徑還是有可能存在的，如果奇數度的頂點多余兩個，連歐拉路徑都不可能存在。

三：如何得到歐拉回路

求解起點和終點重合的歐拉回路問題可以基于深度優先思想來實現，與DFS算法的區別就是，DFS算法中每個節點基本上只會訪問一遍，而歐拉回路算法中要求放寬，只是每個邊只能訪問一邊，但是某一個節點可以多次訪問，但基本思想是一致的。DFS算法

深度優先搜索的主要問題在于當訪問返回開始節點時，可能還剩下某些邊沒有訪問到，也就是訪問提前結束了，比較好補救方法就是，在那些沒有訪問到的路徑的第一個節點重新開始新一輪深度優先搜索，將新的回路加到原來回路中，繼續此過程直到所有的邊都被遍歷為止

四：Java實現

import java.util.*;/*** @author ht113*/ public class EulerCircuit {private List<Integer> path;/*** this cost O(|E| + |V|) time* @param unDirectedEdges: adjacency matrix,[1,2] represents edge from node1 to node2* @param n: the num of nodes* @param k: the start node of Euler Circuit* @return* @throws NotFoundException*/public List<Integer> EulerCircuitByDFS(int[][] unDirectedEdges, int n, int k) throws NotFoundException{if (unDirectedEdges==null||unDirectedEdges.length<=1||n<=2) {throw new NotFoundException();}//init undirected graph,use adjacency list//{key:1, value:<2, 3>} represents edge from node1 to node2,node3Map<Integer, List<Integer>> graph = new HashMap<>();//making graph takes O(E)//iterate the adjacency matrixfor(int i = 0; i<unDirectedEdges.length; i++) {int[] edge = unDirectedEdges[i];//add (edge[0], edge[1])if (!graph.containsKey(edge[0])) {graph.put(edge[0], new ArrayList<Integer>());}graph.get(edge[0]).add(edge[1]);//add (edge[1], edge[0])if (!graph.containsKey(edge[1])) {graph.put(edge[1], new ArrayList<Integer>());}graph.get(edge[1]).add(edge[0]);}path = new ArrayList<>();//ECDFS takes O(V)try {ECDFS(graph, k, k, path);}catch (NotFoundException e){throw e;}return path;}/*** special dfs for Euler Circuit* @param graph* @param k: start node* @param origin: the origin start node* @param currentPath* @throws NotFoundException*/public void ECDFS(Map<Integer, List<Integer>> graph, int k, int origin, List<Integer> currentPath)throws NotFoundException{currentPath.add(k);for(int i = 0; i<graph.get(k).size(); i++){int neighbor = graph.get(k).get(i);//and the degree of node w is oddif(neighbor!=origin && graph.get(neighbor).size()%2!=0){throw new NotFoundException();}graph.get(k).remove(i);graph.get(neighbor).remove(Integer.valueOf(k));//when dfs return to the origin start node//some edges may not have been visitedif(neighbor==origin){currentPath.add(origin);boolean allSeen;do{boolean tmp = true;for(int j = 0; j<currentPath.size(); j++) {int entryNode = currentPath.get(j);tmp &= graph.get(entryNode).size() == 0;if(!tmp) {List<Integer> tempPath = new ArrayList<>();ECDFS(graph, entryNode, entryNode , tempPath);//add child circuit pathint index = currentPath.indexOf(entryNode);currentPath.remove(index);currentPath.addAll(index, tempPath);}}allSeen = tmp;}while (!allSeen);return;}else {ECDFS(graph, neighbor, origin, currentPath);}}}public static class NotFoundException extends Exception{public NotFoundException(){super("Euler Circuit Not Found");}}}

測試：

輸入：

unDirectedEdgesnk

{{1,3}, {1,4}, {2,3}, {2,8}, {3,4}, {3,6}, {3,7},{3,9}, {4,5}, {4,7}, {4,10}, {4,11}, {5,10}, {6,9}, {7,9},{7,10}, {8,9}, {9,10}, {9,12}, {10,11}, {10,12}}	12	5
{{1,3},{1,2},{3,4}, {2,3}, {2,4}};	4	4

預計輸出：
某一條從節點5開始節點5結束的歐拉回路

Euler Circuit Not Found

實際輸出：
[5, 4, 1, 3, 2, 8, 9, 10, 12, 9, 3, 4, 7, 3, 6, 9, 7, 10, 4, 11, 10, 5]

Euler Circuit Not Found

測試通過

---

你可能還敢興趣的圖論算法(均附Java實現代碼)：

• 算法實驗–主函數只有五行的Floyed的算法以及最短路徑輸出

• 你必須會的–Dijkstra算法–單源最短路徑問題

• 你必須會的DFS的遞歸實現與堆棧實現

• 你必須會的啟發式搜索算法–A*算法

總結

以上是生活随笔為你收集整理的你了解欧拉回路吗？（附Java实现代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

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