歐拉回路

歐拉回路 【定義】 圖G的一個迴路，若它恰通過G中每條邊一次,則稱該回路為歐拉(Euler)迴路。 具有歐拉回路的圖稱為歐拉圖（簡稱E圖）。 【相關結論】 定理： 一個無向圖是歐拉圖，當且僅當該圖所有頂點度數都是偶數或只有兩個定點的度數為奇。 一個有向圖是歐拉圖，當且僅當該圖所有頂點度數都是0。 求歐拉回路的一種解法 下面是無向圖的歐拉回路輸出代碼：注意輸出的前提是已經判斷圖確實是歐拉回路。 int num = 0;//標記輸出隊列 int match

\[MAX\]

;//標誌節點的度，無向圖，不區分入度和出度 void solve(int x) { if(match

\[x\]

== 0)

Record

\[num++\]

= x;

else { for(int k =0;k<=500;k++) { if(Array

\[x\] \[k\]

!=0 ) { Array

\[x\] \[k\]

–; Array

\[k\] \[x\]

–; match

\[x\]

–; match

\[k\]

–; solve(k); }

} Record

\[num++\]

= x; } } 注意record中的點的排列是輸出的到序，因此，如果要輸出歐拉路徑，需要將record倒過來輸出。 求歐拉回路的思路： 循環的找到出發點。從某個節點開始，然後查出一個從這個出發回到這個點的環路徑。這種方法保證每個邊都被遍歷。如果有某個點的邊沒有被遍歷就讓這個點為起點，這條邊為起始邊，把它和當前的環銜接上。這樣直至所有的邊都被遍歷。這樣，整個圖就被連接到一起了。 具體步驟： 1。如果此時與該點無相連的點，那麼就加入路徑中 2。如果該點有相連的點，那馬就列一張表，遍歷這些點，知道沒有相連的點。 3。處理當前的點，刪除走過的這條邊，並在其相鄰的點上進行同樣的操作，並把刪除的點加入到路徑中去。 4。這個其實是個遞歸過程。