在18世紀，東普魯士哥尼斯堡有一條大河，河中有兩個小島。全城被大河分割成四塊陸地，河上架有七座橋，把四塊陸地聯系起來(如圖)。當時許多市民都在思索一個問題:一個散步者能否從某一陸地出發，不重復地經過每座橋一次，最后回到原來的出發地。

七橋問題：

這就是歷史上有名的哥尼斯堡七橋問題。

這個問題似乎不難解決，所以吸引了許多人來嘗試，但是日復一日誰也沒有得出肯定的答案。于是有人便寫信求教當時著名的數學家歐拉(1707~1783)。歐拉畢竟是數學家，他并沒有去重復人們已失敗了多次的試驗，而是產生了一種直覺的猜想:人們千百次的失敗，也許意味著這樣的走法根本就不存在。于是歐拉把七橋問題進行了數學的抽象。用A、B、C、D四個點表示四塊陸地，用兩點間的一條線表示連接兩塊陸地之間的一座橋，就得到如下圖所示的一個由四個點和七條線組成的圖形。

于是，七橋問題就轉化為一個抽象圖形是否可以“一筆畫”的問題。
這個一筆畫，也是歐拉回路的判定方法是這樣的：

• 連通多重圖具有歐拉路當且僅當它有0個或2個度數為奇數的結點。
• 連通多重圖具有歐拉路但無歐拉回路當且僅當它有2個度數為奇數的結點。
• 連通多重圖具有歐拉回路當且僅當它只有度數為偶數的結點。

所以我們依據

歐拉大神tql，下面是對問題的再進一步抽象（用二維數組表示的矩陣）：

下面是Java代碼實現：

public class EulerCircuit {//定義二維數組實現圖儲存int[][] mat;//定義頂點個數int vertexNum;//構造函數問題初始化public EulerCircuit(int[][] mat, int vertexNum) {super();this.mat = mat;this.vertexNum = vertexNum;}public int getOddVertexNum() {//累加器記錄奇數頂點個數int count = 0;//依次累加每一行元素for (int i = 0; i < vertexNum; i++) {//記錄通過頂點i的邊數int degree = 0;for (int j = 0; j < vertexNum; j++) {degree += mat[i][j];}//頂點度為奇數時if (degree % 2 != 0) {count++;}}//結束函數，返回奇數頂點個數return count;}public static void main(String[] args) {//七橋問題數組int[][] mat = {{0, 1, 2, 2}, {1, 0, 1, 1}, {2, 1, 0, 0}, {2, 1, 0, 0}};//生成EulerCircuit對象EulerCircuit eulerCircuit = new EulerCircuit(mat, 4);//根據函數獲取奇數橋的個數int oddVertexNum = eulerCircuit.getOddVertexNum();if (oddVertexNum == 0) {System.out.println("有歐拉回路");} else {System.out.println("有" + oddVertexNum + "個頂點通奇數橋，無歐拉回路");}}}

如果求歐拉路就可以設置條件判定的分叉點為2

總結

以上是生活随笔為你收集整理的【Java】欧拉回路的判定的全部內容，希望文章能夠幫你解決所遇到的問題。

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