天天看點

【説明する】一筆畫

考試的方面:

(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

代碼~

如果運氣好也是錯,那我倒願意錯上加錯!

❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀❀