国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

圖論教學(xué)中求最小生成樹的方法研究

2020-01-07 00:45丁學(xué)利

丁學(xué)利

摘 ?要:對圖論教學(xué)中尋找最小生成樹的常用三種算法進(jìn)行論述,并結(jié)合實例對三種算法進(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

樹是一種特殊的圖,在實際生活中應(yīng)用廣泛,如生成樹、決策樹、游戲樹等。學(xué)界針對最小生成樹的求法進(jìn)行了深入研究和探討,如Kruskal (克魯斯克爾)于1956年最先給出了一種求最小生成樹的算法,即避圈法[1];隨后Prim(普里姆)于1957年給出了Prim算法[2];我國學(xué)者管梅谷于1975年給出了破圈法[3]等。在圖論教材[4]中一般對避圈法進(jìn)行了詳細(xì)介紹,而對其它算法介紹較少。本文以《計算機數(shù)學(xué)》圖論中尋找最小生成樹的方法為切入點,結(jié)合實例深入探討求最小生成樹的三種算法。同時指出在教學(xué)中,即要系統(tǒng)詳細(xì)地講解基本概念,還要通過范例擴展學(xué)生的視野,從不同視角培養(yǎng)學(xué)生的發(fā)散思維和創(chuàng)新思維能力。

1 最小生成樹[4]的概念

在一個連通圖 中,稱無圈的連通圖為樹,稱包含圖 全部頂點的樹為圖 的生成樹。生成樹上各邊的權(quán)之和稱為該生成樹的權(quán)。連通圖 的權(quán)最小的生成樹稱為圖 的最小生成樹。

根據(jù)上述定義,要確保如下兩個方面:(1)在尋找權(quán)最小的邊時,要保證不能出現(xiàn)回路;(2)若圖 含有 個頂點,則尋找的 條邊恰能將原圖的所有頂點連通。

2 方法

2.1 避圈法

避圈法[1,5,6]是Kruskal于1956年提出的一種高效的尋找方法,即從圖 的權(quán)值最小的邊開始找,進(jìn)行避圈式擴張,步驟如下:

(1)首先選取 中權(quán)值最小的邊 (若有多個權(quán)最小的邊,任選一個權(quán)最小的邊),同時記該邊 和其兩個端點的圖為 ;

(2)如果已選取邊 ,那么再從 中選取邊 ,使邊 的權(quán)值最小且保證得到的 為無圈圖。

(3)當(dāng)圖 的所有頂點都納入到了 中,則停止,否則重復(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]的基本思路是通過逐個連接頂點的方法。一開始去掉所有的邊,從任一頂點開始逐個連接,最終將所有頂點連接,算法結(jié)束。

Prim算法步驟如下:

(1)設(shè)置一個頂點集 和邊集 。初始時,在 中任意取一個頂點 ,令 , ?;

(2)選取與某個 鄰接的頂點 ,使邊 (頂點 與 相連的邊)的權(quán)值最小,令 , ;

(3)若所有的頂點都連接,則停止,否則重復(fù)第(2)步。

3 實例分析

某新建小區(qū)要鋪設(shè)供水管道,其分布圖如圖1。圖1中 ( )表示每棟樓要接入供水管道的位置,連線上的數(shù)字表示它們之間的距離,試給出線路總長最短的鋪設(shè)方案。

本題可看作是一個帶權(quán)無向連通圖 。怎樣鋪設(shè)才能使線路總長最短,其本質(zhì)就是計算圖1的最小生成樹。下面分別利用避圈法、破圈法和Prim算法給出計算結(jié)果。

3.1 避圈法求解

避圈法的計算步驟如下:

(1)初始時,挑選最小邊 ,用粗實線標(biāo)識邊 。記邊集 ,得圖2(a)。

(2)在余下的邊中,有兩個權(quán)值最小的邊: 和 。任選一個,不妨選邊 ,用粗實線標(biāo)識邊 。更新 ,得圖2(b)。

(3)在剩余的邊中尋找最小且無回路的邊,權(quán)值最小的邊是 ,用粗實線標(biāo)識邊 。更新 ,得圖2(c)。

(4)在剩余的邊中尋找,發(fā)現(xiàn)邊 符合條件,用粗實線標(biāo)識邊 。更新 ,得圖2(d)。

(5)繼續(xù)在剩余的邊中尋找,發(fā)現(xiàn)邊 符合條件,用粗實線標(biāo)識邊 。更新 ,得圖2(e)。

(6)繼續(xù)在剩余的邊中尋找,發(fā)現(xiàn)邊 符合條件,用粗實線標(biāo)識邊 。更新 ,得圖2(f)。

此時圖 中包含了圖 的所有頂點,算法結(jié)束。最短鋪設(shè)方案如圖2(f)中粗實線所示,其最短路線總長為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)初始時,任選一個頂點,如選頂點 。定義新的 , 。

(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)。

此時訪問了所有頂點,算法結(jié)束,圖4(f)即為所求。

4 三種算法的比較[10,11]

避圈法的每一步都能得到最優(yōu)解,因此它是一種精確求解算法。同時,該方法只是對圖的邊進(jìn)行查找,這種算法的復(fù)雜度只與邊數(shù)有關(guān)系,因此該方法較適合求解邊稀疏的稀疏圖。而當(dāng)圖的邊數(shù)較多且規(guī)模較大時,其求解最小生成樹的速度會變慢。

破圈法是從圖 開始,通過逐步破除掉每個圈中最大的邊,生成最小生成樹。破圈法較適合直接在圖上尋找最小生成樹,當(dāng)圖的規(guī)模較大時,可安排若干個人對各個子圖同時進(jìn)行破圈,因此該方法很方便、實用。

Prim算法是從空圖 開始,將頂點逐個連通的方式來尋找最小生成樹的,因此Prim算法的復(fù)雜度只與頂點數(shù)有關(guān),較適合邊數(shù)較多的稠密圖。但它是一種近似求解算法,實際應(yīng)用時得到的不一定是最優(yōu)解,因此求解時需注意。

破圈法和避圈法的本質(zhì)是一樣的,都是盡可能刪掉權(quán)值大的邊。Prim算法和避圈法本質(zhì)都是貪心算法。避圈法需要先對權(quán)值排序后查找,但只需一次對權(quán)值排序后就可以找到最小生成樹。雖然Prim算法是直接查找法,但需要多次對鄰邊排序才能找到,因此避圈法比Prim算法效率更高。

5 結(jié)束語

本文探討了圖論中尋找最小生成樹常用的三種算法,并結(jié)合實例討論了三種算法的優(yōu)缺點。除了這三種算法之外,還有矩陣計算法[12]、逐步短接法[13]等。因此,在教學(xué)中,應(yīng)以此類問題的研究和討論為依托,從不同視角訓(xùn)練學(xué)生的發(fā)散思維,這樣既有利于學(xué)生對概念和算法的深入理解,也有助于學(xué)生編程實現(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é)的實踐與認(rèn)識[J].1975(4):38-41.

[4]周忠榮.計算機數(shù)學(xué)[M].3版.北京:清華大學(xué)出版社,2014:191-193.

[5]王偉,孟思燕.Kruskal算法的研究與改進(jìn)[J].重慶文理學(xué)院學(xué)報(自然科學(xué)版),2010,29(3):25-27.

[6]孫凌宇,冷明,譚云蘭,等.賦權(quán)有向圖的最小生成樹算法[J].計算機工程,2010,36(2):61-63.

[7]閆超君.破圈法應(yīng)用中的誤區(qū)分析[J].河北工程大學(xué)學(xué)報(自然科學(xué)版),2012,29(2):65-74.

[8]劉朝霞.改進(jìn)的Prim算法在求解旅行商問題中的應(yīng)用[J].陰山學(xué)刊,2015,29(1):8-10.

[9]江波,張黎.基于Prim算法的最小生成樹優(yōu)化研究[J].計算機工程與設(shè)計, 2009,30(13):3244-3247.

[10]張愛平,李強,陳志彬.最優(yōu)樹算法的教學(xué)研究[J].當(dāng)代教育理論與實踐,2013,5(10):75-77.

[11]胥桂仙,駱賓杰,趙晨曦,等.離散數(shù)學(xué)實踐教學(xué)探索[J].中央民族大學(xué)學(xué)報(自然科學(xué)版),2016,25(3):61-67.

[12]毛華,史田敏,高瑞.求最小生成樹的矩陣算法[J].鄭州大學(xué)學(xué)報(理學(xué)版),2013,45(4):23-25.

[13]張亞蕾.最大生成樹算法及其應(yīng)用的研究[J].河南教育學(xué)院學(xué)報(自然科學(xué)版),2019,28(2):14-20.

轮台县| 花莲县| 广水市| 兴义市| 义乌市| 洪泽县| 云林县| 美姑县| 芮城县| 潍坊市| 新绛县| 壤塘县| 囊谦县| 长宁区| 个旧市| 文安县| 准格尔旗| 多伦县| 专栏| 句容市| 文成县| 克什克腾旗| 滕州市| 黄冈市| 奈曼旗| 灵武市| 丹江口市| 文安县| 湘潭县| 石景山区| 谢通门县| 图们市| 喀喇沁旗| 屏东县| 武安市| 枝江市| 无为县| 桑日县| 杂多县| 陕西省| 沙坪坝区|