問題2 一筆畫問題

哥尼斯堡七橋問題

圖論

歐拉

這幾個(gè)詞，不知道，非計(jì)算機(jī)專業(yè)的人知道幾個(gè)。

如果不知道，建議在智能手機(jī)上安裝“一筆畫”這個(gè)游戲APP，玩一玩，算一個(gè)智力休閑游戲吧。然后百度一下哥尼斯堡七橋問題，了解一下圖論的起源，了解圖論之父歐拉。

?

要描述一筆畫問題，必須使用圖論中的術(shù)語。

一筆畫問題：能否從一個(gè)節(jié)點(diǎn)開始，沿著一條邊到它的某一個(gè)相鄰節(jié)點(diǎn)，如此繼續(xù)，最后返回出發(fā)節(jié)點(diǎn)，中間每條邊恰好經(jīng)過1次。

?

歐拉提出的歐拉定理，可以判斷一個(gè)圖是否可以實(shí)現(xiàn)“一筆畫”。

?

求一個(gè)歐拉圖的歐拉路徑，也就是求一筆畫。有兩個(gè)有名的算法：

?

一個(gè)是Fleury算法，這個(gè)算法的算法思想，是不斷刪除邊，但要保證留下的圖總保持是歐拉圖（去掉孤立節(jié)點(diǎn)），且當(dāng)前節(jié)點(diǎn)是算法的合法起始節(jié)點(diǎn)。書中詳細(xì)描述了Fleury算法，還用歸納法給出了算法正確性證明描述。這個(gè)算法的思想比較容易理解，簡單說，就是如果把走過的邊，因?yàn)椴荒茉僮吡?，看作刪除，那每走一步，不能讓剩余的圖變?yōu)椴贿B通圖，否則就無法走完所有邊。這個(gè)利用圖論中，橋的概念，就容易設(shè)計(jì)出算法。但是這個(gè)算法的性能不佳。

另一個(gè)是Hierholzer算法，簡單說，這個(gè)算法是利用圖的深度優(yōu)先算法，不斷找環(huán)路，然后刪除環(huán)路，最終可以求得歐拉路徑。估計(jì)是設(shè)計(jì)太多圖論、數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)，本書沒有說明。

另外，本章也提到了著名的“中國郵遞員問題”，有興趣的讀者，可以自己百度Hierholzer算法和中國郵遞員問題，進(jìn)行擴(kuò)展閱讀。

?

?

【作者感受】

圖和圖的算法，是計(jì)算機(jī)核心課程中重點(diǎn)核心內(nèi)容之一。

圖，即看的見，又看不見，數(shù)學(xué)中有圖論，計(jì)算機(jī)實(shí)現(xiàn)圖的求解算法都很燒腦，能夠?qū)W習(xí)和感受圖算法的美，真好。