圖論教學(xué)中求最小生成樹的方法研究
2020-01-07 00:45:08丁學(xué)利
丁學(xué)利
摘 ?要：對圖論教學(xué)中尋找最小生成樹的常用三種算法進(jìn)行論述，并結(jié)合實(shí)例對三種算法進(jìn)行對比分析。同時指出在圖論相關(guān)教學(xué)中應(yīng)積極培養(yǎng)學(xué)生創(chuàng)新思考和多視角分析解決問題的能力。
關(guān)鍵詞：最小生成樹;避圈法;破圈法;Prim算法
中圖分類號：O157.5 ? ? ? ? 文獻(xiàn)標(biāo)識碼：A ? ? ? ? ? 文章編號：1672-4437（2020）04-0039-04
樹是一種特殊的圖，在實(shí)際生活中應(yīng)用廣泛，如生成樹、決策樹、游戲樹等。學(xué)界針對最小生成樹的求法進(jìn)行了深入研究和探討，如Kruskal （克魯斯克爾）于1956年最先給出了一種求最小生成樹的算法，即避圈法[1];隨后Prim（普里姆）于1957年給出了Prim算法[2];我國學(xué)者管梅谷于1975年給出了破圈法[3]等。在圖論教材[4]中一般對避圈法進(jìn)行了詳細(xì)介紹，而對其它算法介紹較少。本文以《計(jì)算機(jī)數(shù)學(xué)》圖論中尋找最小生成樹的方法為切入點(diǎn)，結(jié)合實(shí)例深入探討求最小生成樹的三種算法。同時指出在教學(xué)中，即要系統(tǒng)詳細(xì)地講解基本概念，還要通過范例擴(kuò)展學(xué)生的視野，從不同視角培養(yǎng)學(xué)生的發(fā)散思維和創(chuàng)新思維能力。
1 最小生成樹[4]的概念
在一個連通圖 中，稱無圈的連通圖為樹，稱包含圖 全部頂點(diǎn)的樹為圖 的生成樹。生成樹上各邊的權(quán)之和稱為該生成樹的權(quán)。連通圖 的權(quán)最小的生成樹稱為圖 的最小生成樹。
根據(jù)上述定義，要確保如下兩個方面：（1）在尋找權(quán)最小的邊時，要保證不能出現(xiàn)回路;（2）若圖 含有 個頂點(diǎn)，則尋找的 條邊恰能將原圖的所有頂點(diǎn)連通。
2 方法
2.1 避圈法
避圈法[1，5，6]是Kruskal于1956年提出的一種高效的尋找方法，即從圖 的權(quán)值最小的邊開始找，進(jìn)行避圈式擴(kuò)張，步驟如下：
（1）首先選取 中權(quán)值最小的邊 （若有多個權(quán)最小的邊，任選一個權(quán)最小的邊），同時記該邊 和其兩個端點(diǎn)的圖為 ;
（2）如果已選取邊 ，那么再從 中選取邊 ，使邊 的權(quán)值最小且保證得到的 為無圈圖。
（3）當(dāng)圖 的所有頂點(diǎn)都納入到了 中，則停止，否則重復(fù)上述的第（2）步。
2.2 破圈法
破圈法[3，7]是我國學(xué)者管梅谷教授在Kruskal算法的基礎(chǔ)上于1975年提出的一種算法。本算法的基本思想是逐步刪除回路中權(quán)值最大的邊，即先任選一個圈，刪掉其中權(quán)值最大的一條邊（如果權(quán)值最大的邊不是一個，可任選一個），稱為破圈，然后再查找下一個圈中權(quán)值最大的邊并刪除。這樣不斷破圈，直至刪除圖 中的所有圈為止，最后剩下的子圖 即為所求。
2.3 Prim算法
Prim（普里姆）算法[2，8，9]的基本思路是通過逐個連接頂點(diǎn)的方法。一開始去掉所有的邊，從任一頂點(diǎn)開始逐個連接，最終將所有頂點(diǎn)連接，算法結(jié)束。
Prim算法步驟如下：
（1）設(shè)置一個頂點(diǎn)集 和邊集 。初始時，在 中任意取一個頂點(diǎn) ，令 ， ?;
（2）選取與某個 鄰接的頂點(diǎn) ，使邊 （頂點(diǎn) 與 相連的邊）的權(quán)值最小，令 ， ;
（3）若所有的頂點(diǎn)都連接，則停止，否則重復(fù)第（2）步。
3 實(shí)例分析
某新建小區(qū)要鋪設(shè)供水管道，其分布圖如圖1。圖1中 （ ）表示每棟樓要接入供水管道的位置，連線上的數(shù)字表示它們之間的距離，試給出線路總長最短的鋪設(shè)方案。
本題可看作是一個帶權(quán)無向連通圖 。怎樣鋪設(shè)才能使線路總長最短，其本質(zhì)就是計(jì)算圖1的最小生成樹。下面分別利用避圈法、破圈法和Prim算法給出計(jì)算結(jié)果。
3.1 避圈法求解
避圈法的計(jì)算步驟如下：
（1）初始時，挑選最小邊 ，用粗實(shí)線標(biāo)識邊 。記邊集 ，得圖2（a）。
（2）在余下的邊中，有兩個權(quán)值最小的邊： 和 。任選一個，不妨選邊 ，用粗實(shí)線標(biāo)識邊 。更新 ，得圖2（b）。
（3）在剩余的邊中尋找最小且無回路的邊，權(quán)值最小的邊是 ，用粗實(shí)線標(biāo)識邊 。更新 ，得圖2（c）。
（4）在剩余的邊中尋找，發(fā)現(xiàn)邊 符合條件，用粗實(shí)線標(biāo)識邊 。更新 ，得圖2（d）。
（5）繼續(xù)在剩余的邊中尋找，發(fā)現(xiàn)邊 符合條件，用粗實(shí)線標(biāo)識邊 。更新 ，得圖2（e）。
（6）繼續(xù)在剩余的邊中尋找，發(fā)現(xiàn)邊 符合條件，用粗實(shí)線標(biāo)識邊 。更新 ，得圖2（f）。
此時圖 中包含了圖 的所有頂點(diǎn)，算法結(jié)束。最短鋪設(shè)方案如圖2（f）中粗實(shí)線所示，其最短路線總長為26。
3.2 破圈法求解
破圈法求解步驟如下：
（1）任選一個圈，如圈 ，刪掉其中權(quán)值最大的邊 ，得圖3（a）。
（2）再從余下的圈中任選一個，如圈 ，刪掉其中權(quán)值最大的邊 ，得圖3（b）。
（3）再從余下的圈中任選一個，如圈 ，其中有兩個邊 和 的權(quán)值一樣大，任選一個刪除，如刪除 ，得圖3（c）。
（4）再從余下的圈中任選一個，如圈 ，刪掉其中權(quán)值最大的邊 ，得圖3（d）。
（5）再從余下的圈中任選一個，如圈 ，刪掉其中權(quán)值最大的邊 ，得圖3（e）。
（6）再從余下的圈 中，刪掉權(quán)值最大的邊 ，得圖3（f）。
此時圖3（f）中所有的圈都破掉了，算法結(jié)束。圖3（f）即為所求。
3.3 Prim算法求解
用Prim算法求解過程如下：
（1）初始時，任選一個頂點(diǎn)，如選頂點(diǎn) 。定義新的 ， 。
（2）從 尋找與之連接的所有邊，權(quán)值最小的邊是 。更新 ， ，見圖4（a）。
（3）從 中尋找與之連接的所有邊，權(quán)值最小的邊是 。更新 ， ，見圖4（b）。
（3）從 中尋找與之連接的所有邊，權(quán)值最小的邊是 。更新 ， ，見圖4（c）。
（4）從 中尋找與之連接的所有邊，權(quán)值最小的邊是 。更新 ， ，見圖4（d）。
（5）從 中尋找與之連接的所有邊，權(quán)值最小的邊是 。更新 ， ，見圖4（e）。
（6）從 中尋找與之連接的所有邊，權(quán)值最小邊是 。更新 ， ，見圖4（f）。
此時訪問了所有頂點(diǎn)，算法結(jié)束，圖4（f）即為所求。
4 三種算法的比較[10，11]
避圈法的每一步都能得到最優(yōu)解，因此它是一種精確求解算法。同時，該方法只是對圖的邊進(jìn)行查找，這種算法的復(fù)雜度只與邊數(shù)有關(guān)系，因此該方法較適合求解邊稀疏的稀疏圖。而當(dāng)圖的邊數(shù)較多且規(guī)模較大時，其求解最小生成樹的速度會變慢。
破圈法是從圖 開始，通過逐步破除掉每個圈中最大的邊，生成最小生成樹。破圈法較適合直接在圖上尋找最小生成樹，當(dāng)圖的規(guī)模較大時，可安排若干個人對各個子圖同時進(jìn)行破圈，因此該方法很方便、實(shí)用。
Prim算法是從空圖 開始，將頂點(diǎn)逐個連通的方式來尋找最小生成樹的，因此Prim算法的復(fù)雜度只與頂點(diǎn)數(shù)有關(guān)，較適合邊數(shù)較多的稠密圖。但它是一種近似求解算法，實(shí)際應(yīng)用時得到的不一定是最優(yōu)解，因此求解時需注意。
破圈法和避圈法的本質(zhì)是一樣的，都是盡可能刪掉權(quán)值大的邊。Prim算法和避圈法本質(zhì)都是貪心算法。避圈法需要先對權(quán)值排序后查找，但只需一次對權(quán)值排序后就可以找到最小生成樹。雖然Prim算法是直接查找法，但需要多次對鄰邊排序才能找到，因此避圈法比Prim算法效率更高。
5 結(jié)束語
本文探討了圖論中尋找最小生成樹常用的三種算法，并結(jié)合實(shí)例討論了三種算法的優(yōu)缺點(diǎn)。除了這三種算法之外，還有矩陣計(jì)算法[12]、逐步短接法[13]等。因此，在教學(xué)中，應(yīng)以此類問題的研究和討論為依托，從不同視角訓(xùn)練學(xué)生的發(fā)散思維，這樣既有利于學(xué)生對概念和算法的深入理解，也有助于學(xué)生編程實(shí)現(xiàn)此算法。
參考文獻(xiàn)：
[1]Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem[J]. Proceedings of the American Mathematical society， 1956，7（1）： 48-50.
[2]Prim R C. Shortest connection networks and some generalizations[J].The Bell System Technical Journal，1957，36（6）：1389-1401.
[3]管梅谷.求最小樹的破圈法數(shù)學(xué)的實(shí)踐與認(rèn)識[J].1975（4）：38-41.
[4]周忠榮.計(jì)算機(jī)數(shù)學(xué)[M].3版.北京：清華大學(xué)出版社，2014：191-193.
[5]王偉，孟思燕.Kruskal算法的研究與改進(jìn)[J].重慶文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2010，29（3）：25-27.
[6]孫凌宇，冷明，譚云蘭，等.賦權(quán)有向圖的最小生成樹算法[J].計(jì)算機(jī)工程，2010，36（2）：61-63.
[7]閆超君.破圈法應(yīng)用中的誤區(qū)分析[J].河北工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，29（2）：65-74.
[8]劉朝霞.改進(jìn)的Prim算法在求解旅行商問題中的應(yīng)用[J].陰山學(xué)刊，2015，29（1）：8-10.
[9]江波，張黎.基于Prim算法的最小生成樹優(yōu)化研究[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2009，30（13）：3244-3247.
[10]張愛平，李強(qiáng)，陳志彬.最優(yōu)樹算法的教學(xué)研究[J].當(dāng)代教育理論與實(shí)踐，2013，5（10）：75-77.
[11]胥桂仙，駱賓杰，趙晨曦，等.離散數(shù)學(xué)實(shí)踐教學(xué)探索[J].中央民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，25（3）：61-67.
[12]毛華，史田敏，高瑞.求最小生成樹的矩陣算法[J].鄭州大學(xué)學(xué)報(bào)（理學(xué)版），2013，45（4）：23-25.
[13]張亞蕾.最大生成樹算法及其應(yīng)用的研究[J].河南教育學(xué)院學(xué)報(bào)（自然科學(xué)版），2019，28（2）：14-20.
