考試的方面:
(1)一筆畫是怎樣畫的(水)
(2)能否實作一筆畫(小技巧)
1)必須連通(有向與無向都必須滿足)
2)有向圖:(歐拉回路)如果出度等于入度,可以從任意點搜尋;
(歐拉路)如果入度大于出度,則一定為終止點,而如果出度大于入度,則一定為開始的點(注意,如果入度與出度之間的內插補點大于一,則一定不能夠形成歐拉路)
3)無向圖:所有點的度數都為偶數時,才能實作歐拉回路||有兩個點為奇數,且這兩個點分别為起止點
一筆畫性質:
■⒈凡是由偶點組成的連通圖,一定可以一筆畫成。畫時可以把任一偶點為起點,最後一定能以這個點為終點畫完此圖。
■⒉凡是隻有兩個奇點的連通圖(其餘都為偶點),一定可以一筆畫成。畫時必須把一個奇點為起點,另一個奇點為終點。
■⒊其他情況的圖都不能一筆畫出。(奇點數除以二便可算出此圖需幾筆畫成。)
求歐拉路的算法很簡單,使用深度優先周遊即可。
根據一筆畫的兩個定理,如果尋找歐拉回路,對任意一個點執行深度優先周遊;找歐拉路,則對一個奇點執行DFS,時間複雜度為O(m+n),m為邊數,n是點數。
l以下是尋找一個圖的歐拉路的算法實作:
但是具有局限性,例如:

還懇請大佬看到能夠給出改進的意見,
這個代碼可能有點啰嗦……
l樣例輸入:第一行n,m,有n個點,m條邊,以下m行描述每條邊連接配接的兩點。
l 5 5
l 1 2
l 2 3
l 3 4
l 4 5
l 5 1
l樣例輸出:歐拉路或歐拉回路
l 1 5 4 3 2 1
代碼~
如果運氣好也是錯,那我倒願意錯上加錯!
❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀