涂鵬，張恒，孫建春，王路

?

基于權(quán)矩陣的通風(fēng)網(wǎng)絡(luò)最小生成樹算法研究

涂鵬1, 2，張恒1，孫建春1，王路2

(1. 西南交通大學(xué) 交通隧道工程教育部重點(diǎn)實(shí)驗(yàn)室，四川 成都 610031；2. 四川交通職業(yè)技術(shù)學(xué)院 道路與橋梁工程系，四川 成都 611130)

為優(yōu)化圖的數(shù)據(jù)存儲結(jié)構(gòu)，縮小最小生成樹構(gòu)造過程的搜尋范圍，提高搜索效率，減小構(gòu)造過程中的判斷，以賦權(quán)有向圖權(quán)矩陣為基礎(chǔ)，結(jié)合最小生成樹性質(zhì)提出用于存儲通風(fēng)網(wǎng)絡(luò)數(shù)據(jù)的表格，并將表格進(jìn)行分區(qū)處理。基于Prim算法和通風(fēng)網(wǎng)絡(luò)數(shù)據(jù)存儲結(jié)構(gòu)，提出通風(fēng)網(wǎng)絡(luò)最小生成樹構(gòu)造方法并編制相應(yīng)程序，結(jié)合具體通風(fēng)網(wǎng)絡(luò)結(jié)構(gòu)以表格方式給出最小生成樹的具體構(gòu)成過程。研究結(jié)果表明：基于權(quán)矩陣的構(gòu)造方法與經(jīng)典Prim算法對工程算例的最小生成樹進(jìn)行構(gòu)造分析所得到結(jié)果是一致的，同時(shí)編制的程序也驗(yàn)證了該方法能夠正確有效地構(gòu)造通風(fēng)網(wǎng)絡(luò)最小生成樹。

通風(fēng)網(wǎng)絡(luò)；最小生成樹；Prim算法；權(quán)矩陣

最小生成樹在圖論分析中具有重要的意義，因此國內(nèi)外學(xué)者對此問題進(jìn)行了深入的研究。在研究無向賦權(quán)圖的最小生成樹方面，最為常用的是避圈法，其代表算法有Kruskal算法、Prim算法及Dijkstra提出的最小生成樹算法[1]。避圈法在生成最小生成過程避免選擇的邊組成回路，國內(nèi)學(xué)者從相反的思路出發(fā)，在構(gòu)造最小生成樹的過程中通過刪除回路上的最大權(quán)值邊，破除圖中的回路，使得圖中不存在回路，從而得到圖的最小生成樹，因?yàn)樵谧钚∩蓸涞臉?gòu)造過程不斷破除圖中的“圈”，因此稱該方法為破圈法[2?3]?？梢钥闯霰苋Ψê推迫Ψㄒ粋€(gè)是“加法”一個(gè)是“減法”，前者通過將要“加”的邊放進(jìn)最小樹生成樹邊集中得到最小生成樹，而后者則是通過對原圖進(jìn)行“減”后得到最小生成樹，無論是避圈法還是破圈法，在最小生成樹的構(gòu)造過程中，都涉及大量的判斷。通風(fēng)網(wǎng)絡(luò)作為典型的賦權(quán)有向圖，其最小生成樹問題研究成果較少。吳文虎等[4]通過研究有向賦權(quán)圖的有向圈的收縮及展開，對有向賦權(quán)圖的最小生成樹構(gòu)造進(jìn)行了一定的研究。馮俊文[5]提出了賦權(quán)有向圖的表格表示法，并基于該表格給出了一種求解最小生成樹的表上作業(yè)法，但采用該表構(gòu)成最小生成樹的過程中涉及大量的判斷及邊的搜尋，范圍較大，存在效率低的問題。王義章[6]通過對Waissi算法進(jìn)行改進(jìn)，提出了一種時(shí)間復(fù)雜度為(2)的通風(fēng)網(wǎng)絡(luò)最小生成樹算法，該算法中也涉及到較多的判斷。孫凌宇等[7]基于賦權(quán)有向圖的最小生成樹性質(zhì)對Prim算法及Kruskal算法進(jìn)行了改進(jìn)，提出了最小生成樹的改進(jìn)算法，但是未給出賦權(quán)有向圖數(shù)據(jù)的存儲結(jié)構(gòu)，無法判斷算法中邊的搜索效率。袁威威[8]通過對Kruskal算法進(jìn)行改進(jìn)提出了一種改進(jìn)的MST生成算法，該算法雖然減小了對邊的搜索范圍，但加大了對節(jié)點(diǎn)的搜索，同時(shí)也存在大量的判斷。徐建軍等[9]根據(jù)最小生成樹的性質(zhì)及定義提出了一種新的最小生成樹算法，該算法能夠有效提高搜尋效率，但要求程序具有較高的判斷能力，編程難度相對較大。綜上可知，優(yōu)化圖的數(shù)據(jù)存儲結(jié)構(gòu)，減小最小生成樹構(gòu)造過程的搜尋范圍，提高搜索效率，減小構(gòu)造過程中的判斷成為通風(fēng)網(wǎng)絡(luò)最小生成樹構(gòu)造方法的優(yōu)化方向。

1 通風(fēng)網(wǎng)絡(luò)及其最小生成樹

通風(fēng)網(wǎng)絡(luò)是一個(gè)有向網(wǎng)絡(luò)，通風(fēng)網(wǎng)絡(luò)中各分支的方向由風(fēng)流方向決定。通常以進(jìn)風(fēng)口為網(wǎng)絡(luò)的起始節(jié)點(diǎn)，出風(fēng)口為終結(jié)點(diǎn)，進(jìn)風(fēng)口與出風(fēng)口均為大氣節(jié)點(diǎn)[9?11]。

在通風(fēng)網(wǎng)絡(luò)分析中，圖論具有重要的作用，圖的本質(zhì)內(nèi)容是頂點(diǎn)和邊的聯(lián)接關(guān)系，也稱為拓?fù)浣Y(jié)構(gòu)關(guān)系。通常采用矩陣來表述圖中的聯(lián)接關(guān)系，對于賦權(quán)圖而言，權(quán)矩陣不僅能夠反映邊與頂點(diǎn)的聯(lián)接關(guān)系，還能夠清楚的反映圖中各邊的權(quán)值大小，權(quán)矩陣的定義如下：

設(shè)=(,)是一個(gè)通風(fēng)網(wǎng)絡(luò)，圖=(,)是一個(gè)連通圖，||=節(jié)點(diǎn)數(shù)，||=邊數(shù)，=(w,j)是一個(gè)×矩陣，行序標(biāo)識為邊的始節(jié)點(diǎn)，列序標(biāo)識為的末節(jié)點(diǎn)，w,j為聯(lián)接節(jié)點(diǎn),的邊的權(quán)值，即為該通風(fēng)網(wǎng)絡(luò)的權(quán)矩陣。

在通風(fēng)網(wǎng)絡(luò)分析中，風(fēng)網(wǎng)的解算、優(yōu)化及調(diào)節(jié)都和生成樹存在密切的關(guān)系，因此通風(fēng)網(wǎng)絡(luò)中生成樹的選擇對于風(fēng)網(wǎng)分析至關(guān)重要。生成樹的定義為：不含回路的連通圖，換言之，從生成樹的任一節(jié)點(diǎn)沿著生成樹的邊都不能回到原點(diǎn)，但可以到達(dá)除原點(diǎn)外的其他節(jié)點(diǎn)。從生成樹的定義可知，通風(fēng)網(wǎng)絡(luò)的生成樹包含通風(fēng)網(wǎng)絡(luò)的全部節(jié)點(diǎn)及部分邊，用數(shù)學(xué)語言描述即為：圖=(,)是一個(gè)通風(fēng)網(wǎng)絡(luò)圖，T是的一棵生成樹，則T=(,E)，EíE。

將生成樹T對應(yīng)的所有邊的風(fēng)阻值累加值作為該生成樹的風(fēng)阻值，記為(T)。從生成樹的定義可知，通風(fēng)網(wǎng)絡(luò)的生成樹不是唯一的，生成樹的風(fēng)阻值也不是唯一的，必定存在一個(gè)最小值，通常將最小值對應(yīng)的生成樹稱為該通風(fēng)網(wǎng)絡(luò)的最小生成樹。

2 最小生成樹性質(zhì)及Prim算法

最小生成樹性質(zhì)如下：設(shè)=(,)是一個(gè)連通圖，頂點(diǎn)集是的真子集(可以任意選取)，CU為頂點(diǎn)集的補(bǔ)集。頂點(diǎn)?，?CU，(,)表示通風(fēng)網(wǎng)絡(luò)圖中聯(lián)接點(diǎn)集與CU的邊集，即(,)?，記邊集(,)中權(quán)值最小的邊為<,，則一定存在的一棵最小生成樹，它以<,為其中一條邊。

該性質(zhì)證明如下：

假設(shè)為圖=(,)的任意一顆最小生成樹，根據(jù)生成樹定義可知，圖與最小生成樹的擁有相同的頂點(diǎn)集。將頂點(diǎn)集分成2部分和CU，(,)為橫跨這2個(gè)點(diǎn)集的邊集，<,為(,)中權(quán)值最小的邊，當(dāng)不包含邊<,時(shí)，將<,添加到樹中，根據(jù)生產(chǎn)樹的定義可知，添加一條邊后生成樹必定含有回路，因此樹將變?yōu)楹芈返淖訄D，并且該回路上有一條不同于<,的邊<′,′>,′?,′?CU。將<′,′>刪去，得到另一顆樹′，即樹′是通過將中的邊<′,′>替換為<,>得到的。由于<,>邊的權(quán)值小于<′,′>邊，故生成樹′的權(quán)值小于生成樹，這與是任意最小生成樹的假設(shè)相矛盾，從而得證。

Robert C. Prim在該性質(zhì)的啟發(fā)下，采用貪心算法提出了用于構(gòu)造最小生成樹的Pirm算法。該算法可表述為：設(shè)=(,)是一個(gè)連通圖，圖的最小生成樹記為，?為已被選擇的點(diǎn)集，?為連通圖中待選的點(diǎn)集，每次選擇連接點(diǎn)集與?的權(quán)值最小的邊<,>，并將其放入中，直到=時(shí)，停止搜尋。

不難發(fā)現(xiàn)，Prim算法構(gòu)造最小生成樹的過程中，每次選擇最小生成樹的邊時(shí)都運(yùn)用了最小生成樹的性質(zhì)，因此所選的邊也必定是最小生成樹的邊。根據(jù)生成樹的性質(zhì)可知，Prim算法選擇的邊集必能構(gòu)成最小生成樹。

3 通風(fēng)網(wǎng)絡(luò)最小生成樹啟發(fā)式構(gòu)造法

算法與數(shù)據(jù)結(jié)構(gòu)間聯(lián)系密切，算法影響著數(shù)據(jù)結(jié)構(gòu)的構(gòu)造，而數(shù)據(jù)結(jié)構(gòu)又是算法的基礎(chǔ)，因此，一個(gè)優(yōu)秀的算法背后必定存在一個(gè)結(jié)構(gòu)合理的數(shù)據(jù)結(jié)構(gòu)[12?14]。受Prim算法啟示，本文提出了一種利用基于權(quán)矩陣的表格來構(gòu)造最小生成樹的方法。

權(quán)矩陣采用行標(biāo)和列標(biāo)表示通風(fēng)網(wǎng)絡(luò)中風(fēng)支的起點(diǎn)和終點(diǎn)，當(dāng)對權(quán)矩陣行及列元素進(jìn)行變換，變換后的權(quán)矩陣的行標(biāo)及列標(biāo)無法再反映風(fēng)支的起點(diǎn)和終點(diǎn)關(guān)系，為了能夠在變換后依舊能夠反映元素對應(yīng)邊的起點(diǎn)和終點(diǎn)關(guān)系，本文提出一種用于表示通風(fēng)網(wǎng)絡(luò)圖的表，該表在權(quán)矩陣的基礎(chǔ)上增加一行及一列，增加的行及列用于記錄風(fēng)支的終點(diǎn)和起點(diǎn)編號，如表1所示。

表1 通風(fēng)網(wǎng)絡(luò)的表格表示

2個(gè)節(jié)點(diǎn)間無直接聯(lián)接時(shí)，對應(yīng)邊的權(quán)值以￥代替，當(dāng)2點(diǎn)間的直接聯(lián)接邊超過1條時(shí)，對應(yīng)位置填寫最小權(quán)值。將該表簡記為=(,)，稱該表為通風(fēng)網(wǎng)絡(luò)=(,)的表，如表2所示。

表2 通風(fēng)網(wǎng)絡(luò)表的分區(qū)

Table 2 Partition of ventilation network table

為了表述方便，將表格進(jìn)行分區(qū)表示，Ⅰ區(qū)為已選節(jié)點(diǎn)組成的局部表，記為Ⅰ=(,W)；Ⅱ區(qū)為未被選中節(jié)點(diǎn)組成的局部表，記為Ⅱ=(?,W?U)；Ⅲ區(qū)為以節(jié)點(diǎn)集中的節(jié)點(diǎn)為起點(diǎn)，以節(jié)點(diǎn)集?中的節(jié)點(diǎn)為終點(diǎn)組成的局部表，記為Ⅲ=(,W,V?)；Ⅳ區(qū)為以節(jié)點(diǎn)集?中的節(jié)點(diǎn)為起點(diǎn)，以節(jié)點(diǎn)集中的節(jié)點(diǎn)為終點(diǎn)組成的局部表，記為Ⅳ=(,W?,U)。

由于最小生成樹的構(gòu)造過程中，與?處于變化中，因此，元素在各分區(qū)的分布也隨著最小生成樹的構(gòu)造過程發(fā)生變化。結(jié)合最小生成樹的性質(zhì)可知，在給定時(shí)，最小生成樹的邊只存于Ⅲ和Ⅳ區(qū)中，不可能存在于Ⅰ和Ⅱ區(qū)。因此可知對通風(fēng)網(wǎng)絡(luò)表進(jìn)行上述分區(qū)能夠有效鎖定最小生成樹邊的范圍，減小搜尋量，提高搜尋效率。搜索效率提高程度與網(wǎng)絡(luò)結(jié)構(gòu)密切相關(guān)，網(wǎng)絡(luò)權(quán)矩陣越稀疏，效率的提高越?。环粗?，效率的提高越明顯。因此，采用本文構(gòu)造的通風(fēng)網(wǎng)絡(luò)表求解最小生成樹的具體過程如下：

第1步：將通風(fēng)網(wǎng)絡(luò)的起點(diǎn)放入點(diǎn)集中，在對應(yīng)的Ⅲ和Ⅳ區(qū)中選擇值最小的元素；

第2步：將新選擇的節(jié)點(diǎn)放入點(diǎn)集中，將對應(yīng)的邊放入中；

第3步：||是否等于|V|；

第4步：第3步滿足要求則完成通風(fēng)網(wǎng)絡(luò)最小生成樹的構(gòu)造，否則，調(diào)整表格后按照第1，2和3步順序循環(huán)。

表格的調(diào)整方法有多種，本文采用的方法如表3和表4所示。若節(jié)點(diǎn)1，2，3已被記入點(diǎn)集中，則此時(shí)通風(fēng)網(wǎng)絡(luò)表的Ⅲ和Ⅳ區(qū)如表3所示；若2,n為Ⅲ和Ⅳ區(qū)中值最小的元素，將第4列與第列進(jìn)行調(diào)換，第4行與第行進(jìn)行調(diào)換，調(diào)換后的表如表4所示。

表3 通風(fēng)網(wǎng)絡(luò)表的調(diào)整方式

Table 3 Adjustment mode of ventilation network table

依據(jù)本文提出的通風(fēng)網(wǎng)絡(luò)最小生成樹構(gòu)造方法，采用C#語言編制了相關(guān)的程序，其操作界面如圖1所示，界面包含1個(gè)數(shù)據(jù)輸入框及3個(gè)按鈕鍵，將通風(fēng)網(wǎng)絡(luò)數(shù)據(jù)按照“起點(diǎn)號，終點(diǎn)號，權(quán)值；起點(diǎn)號，終點(diǎn)號，權(quán)值…；起點(diǎn)號，終點(diǎn)號，權(quán)值”格式輸入數(shù)據(jù)輸入框，按下“添加”鍵完成通風(fēng)網(wǎng)絡(luò)數(shù)據(jù)的輸入操作；按下“顯示通風(fēng)網(wǎng)絡(luò)表”鍵后則可以查看通風(fēng)網(wǎng)絡(luò)表；按下“輸出最小生成樹”鍵則可以得到通風(fēng)網(wǎng)絡(luò)的最小生成樹。MST程序不僅適用于小型風(fēng)網(wǎng)最小生成樹的求解，同時(shí)也能夠用于生成大型風(fēng)網(wǎng)的最小生成樹；與較傳統(tǒng)方法相比，風(fēng)網(wǎng)結(jié)構(gòu)越復(fù)雜，最小生成樹的生成效率越高。搜索效率示意圖如圖2所示，黑色節(jié)點(diǎn)代表已選節(jié)點(diǎn)，共6個(gè)，灰色為待選節(jié)點(diǎn)，共4個(gè)；共16條邊。因?yàn)?個(gè)節(jié)點(diǎn)需5條邊才能連起來，故黑線中應(yīng)該有5條邊已經(jīng)被選取。按照傳統(tǒng)方法共計(jì)11條邊為搜尋范圍，而采用分區(qū)方法后只需要搜尋5條邊(粗線部分)。

表4 調(diào)整后的通風(fēng)網(wǎng)絡(luò)表

圖1 最小生成樹生成軟件操作界面

圖2 搜索效率示意圖

4 工程算例分析

以文獻(xiàn)[15]中的通風(fēng)網(wǎng)絡(luò)圖為工程背景，對本文提出的通風(fēng)網(wǎng)絡(luò)最小生成樹構(gòu)造方法進(jìn)行分析，并與文獻(xiàn)[6]結(jié)果進(jìn)行對比驗(yàn)證。通風(fēng)網(wǎng)絡(luò)中共計(jì)12個(gè)節(jié)點(diǎn)(通風(fēng)網(wǎng)絡(luò)的起點(diǎn)及終點(diǎn)視為2個(gè)節(jié)點(diǎn))，19條分支。其中節(jié)點(diǎn)9與節(jié)點(diǎn)10間存在2條分支，各分支對應(yīng)的權(quán)值見圖2所示。

根據(jù)本文規(guī)定將各分支的權(quán)值記入圖3所示通風(fēng)網(wǎng)絡(luò)表中，得到圖3所示通風(fēng)網(wǎng)絡(luò)表如表5所示。

圖4為圖3所示通風(fēng)網(wǎng)絡(luò)最小生成樹的Prim算法。從通風(fēng)網(wǎng)絡(luò)圖中任選一節(jié)點(diǎn)作為最小生成樹構(gòu)造過程中的已選節(jié)點(diǎn)(節(jié)點(diǎn)1)，如圖4(a)所示；掃描與節(jié)點(diǎn)1聯(lián)接的邊，找到權(quán)值最小的邊<1,3>，將該分支作為最小生成的邊繪制在圖中，如圖4(b)所示；掃描與節(jié)點(diǎn)1、3聯(lián)接的邊，選擇權(quán)值最小的(不包含已選邊)邊<3,6>，同樣作為最小生成的邊繪制在圖中，如圖4(c)所示；掃描與節(jié)點(diǎn)1，3和6聯(lián)接的邊，選擇權(quán)值最小的邊作為最小生成樹的邊繪制在圖3中，如此循環(huán)，直到圖4包含圖3的所有節(jié)點(diǎn)才結(jié)束循環(huán)，完成通風(fēng)網(wǎng)絡(luò)最小生成樹的構(gòu)造過程。圖4(i)即為圖3所示通風(fēng)網(wǎng)絡(luò)的一棵最小生成樹。該生成樹包含的邊為：<1,3>，<3,6>，<6,5>，<5,8>，<6,7>，<1,2>，<7,9>，<9,10>，<10,11>，<11,12>，<4,12>，權(quán)值為0.206 62。

圖3 算例的風(fēng)路風(fēng)阻

表5 算例通風(fēng)網(wǎng)絡(luò)表

圖4 算例通風(fēng)網(wǎng)絡(luò)最小生成樹形成過程圖

表6為采用本文提出的最小生成樹的構(gòu)造方法得到的圖3所示通風(fēng)網(wǎng)絡(luò)的最小生成樹的構(gòu)造過程，對比表6與圖3可知，表6是圖3的表格表現(xiàn)形式，而圖3是表6的圖的表現(xiàn)形式，其對應(yīng)關(guān)系如表7所示。表7也從另一個(gè)方面證明了本文提出的通風(fēng)網(wǎng)絡(luò)最小生成樹的構(gòu)成方法是可行的。

表6 工程算例最小生成樹構(gòu)造過程表

表7 圖3與表6對應(yīng)關(guān)系表

注：為了表述簡潔，表中對圖編號進(jìn)行簡寫，如5 a)簡寫為a)

采用本文提出的方法及Prim算法得出的圖3所示的通風(fēng)網(wǎng)絡(luò)的最小生成樹的權(quán)值為0.206 62。而文獻(xiàn)[6]得到的最小生成樹為：{<1,3>,<1,2><3,6>, <2,4>,<6,5>,<6.7>,<4,12>,<5,8>,<7,9>,<9,10>,<10,11>}，對應(yīng)的權(quán)值為0.368 82。對比可知采用本文方法得到的圖3的最小生成樹權(quán)值較文獻(xiàn)[6]得到的最小生成樹權(quán)值要小，文獻(xiàn)[6]采用除通風(fēng)網(wǎng)絡(luò)的起始節(jié)點(diǎn)外，其他節(jié)點(diǎn)入度(以該節(jié)點(diǎn)為末節(jié)點(diǎn)的邊數(shù)目)為1作為算法的控制條件，得出了圖3所示的通風(fēng)網(wǎng)絡(luò)的最小生成樹。而根據(jù)圖3可知，通風(fēng)網(wǎng)絡(luò)的最小生成樹的節(jié)點(diǎn)的入度可以不為1(圖3節(jié)點(diǎn)12的入度為2)，因此采用節(jié)點(diǎn)入度控制方法不能確保所選的邊為最小生成樹的邊。

圖5為根據(jù)本文提出的最小生成樹構(gòu)造法編制的程序得出的圖3所示通風(fēng)網(wǎng)絡(luò)的最小生成樹，與表6結(jié)果一致。表明該程序編制正確，能夠正確求解通風(fēng)網(wǎng)絡(luò)的最小生成樹。

圖5 軟件生成的最小生成樹

5 結(jié)論

1) 通過在通風(fēng)網(wǎng)絡(luò)圖的權(quán)矩陣中增加一行及一列用于記錄通風(fēng)網(wǎng)絡(luò)分支的起點(diǎn)編號及終點(diǎn)編號，提出了用于表示通風(fēng)網(wǎng)絡(luò)的表。

2) 為了減小通風(fēng)網(wǎng)絡(luò)最小生成樹構(gòu)造過程中邊的搜尋范圍，根據(jù)最小生成樹的性質(zhì)將通風(fēng)網(wǎng)絡(luò)表進(jìn)行了分區(qū)處理，從而將搜尋范圍限定在表中的III、IV區(qū)，極大的減小了最小生成樹構(gòu)成過程中的搜索范圍，提高了搜索效率。

3) 基于權(quán)矩陣的構(gòu)造方法與經(jīng)典Prim算法對工程算例的最小生成樹進(jìn)行了構(gòu)造分析所得到結(jié)果是一致的，同時(shí)編制的程序也驗(yàn)證了該方法能夠正確有效的構(gòu)造通風(fēng)網(wǎng)絡(luò)最小生成樹。

基于權(quán)矩陣的通風(fēng)網(wǎng)絡(luò)最小生成樹構(gòu)造方法雖然縮小了最小生成樹生成過程中的搜尋范圍，提高了搜尋效率，但是對于稀疏權(quán)矩陣而言，由于存在大量的權(quán)值為∞的元素，導(dǎo)致搜尋效率不高，因此，如何提高稀疏權(quán)矩陣的搜尋效率需要進(jìn)一步研究。由于Kruskal算法對于稀疏矩陣有著顯著優(yōu)勢，可嘗試采用本文方法來改進(jìn)Kruskal算法，從而擴(kuò)大算法的適應(yīng)性。

[1] 盧開澄, 盧明華. 圖論及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 1995. LU Kaicheng, LU Minghua. Graph theory and its application[M]. Beijing: Tsinghua University Press, 1995.

[2] 董躍華, 李云浩, 姜在東. 用破圈法實(shí)現(xiàn)普里姆算法[J]. 江西理工大學(xué)學(xué)報(bào), 2008(4): 20?22. DONG Yuehua, LI Yunhao, JIANG Zaidong. Realize prim algorithm with the breaking circle way[J]. Journal of Jiangxi University of Science and Technology, 2008(4): 20?22.

[3] 秦彥新, 王越光. 用“破圈法”求全部最小生成樹的算法[J]. 空軍雷達(dá)學(xué)院學(xué)報(bào), 2006(2): 134?137. QIN Yanxin, WANG Yueguang. Algorithm of finding all minimum spanning trees by breaking loop[J]. Journal of Air Force Radar Academy, 2006(2): 134?137.

[4] 吳文虎, 王建德. 信息學(xué)奧林匹克競賽指導(dǎo)——圖論的算法與程序設(shè)計(jì)[M]. 北京: 清華大學(xué)出版社, 1997. WU Wenhu, WANG Jiande. Information olympiad competition guidance-graph theory and programming [M]. Beijing: Tsinghua University Press, 1997.

[5] 馮俊文. 賦權(quán)有向圖最小生成樹的表上作業(yè)法[J]. 系統(tǒng)工程與電子技術(shù), 1998, 8(6): 26?29. FENG Junwen. Table operations method for minimum spanning trees problem in weighted digraph[J]. Systems Engineering and Electronics, 1998, 8(6): 26?29.

[6] 王義章. 通風(fēng)網(wǎng)絡(luò)中最小生成樹的(~2)算法[J]. 貴州科學(xué), 1995(2): 15?20. WANG Yizhang. The algorithm of(~2) minimum spanning tree and its application in ventilation networks [J]. Guizhou Science, 1995(2): 15?20.

[7] 孫凌宇, 冷明, 譚云蘭, 等. 賦權(quán)有向圖的最小生成樹算法[J]. 計(jì)算機(jī)工程, 2010(2): 61?63, 66. SUN Lingyu, LENG Ming, TAN Yunlan, et al. Minimum spanning tree algorithm for weighted directed graph [J]. Computer Engineering, 2010(2): 61?63, 66.

[8] 袁威威. 應(yīng)用Kruskal的改進(jìn)算法求最小生成樹[J]. 江蘇第二師范學(xué)院學(xué)報(bào), 2017, 33(6): 12?13. YUAN Weiwei. Application of Kruskal’s Improved algorithm to find minimum spanning tree[J]. Journal of Jiangsu Second Normal University (Natural Science), 2017, 33(6): 12?13.

[9] 徐建軍, 沙力妮, 張艷, 等. 一種新的最小生成樹算法[J]. 電力系統(tǒng)保護(hù)與控制, 2011, 39(14): 107?112. XU Jianjun, SHA Lini, ZHANG Yan, et al. A new algorithm for minimum spanning tree[J]. Power System Protection and Control, 2011, 39(14): 107?112.

[10] 鐘德云, 王李管, 畢林, 等. 基于回路風(fēng)量法的復(fù)雜礦井通風(fēng)網(wǎng)絡(luò)解算算法[J]. 煤炭學(xué)報(bào), 2015, 40(2): 365?370. ZHONG Deyun, WANG Liguan, BI Lin, et al. Algorithm of complex ventilation network solution based on circuit air-quantity method[J]. Journal of China Coal Society, 2015, 40(2): 365?370.

[11] Zhong C, Miao D, Wang R. A graph-theoretical clustering method based on two rounds of minimum spanning trees[J]. Pattern Recognition, 2010, 43 (3): 752?766.

[12] Jothi R, Mohanty S K, Ojha A. Functional grouping of imilar genes using eigenanalysis on minimum spanning tree based neighborhood graph[J]. Computers in Biology and Medicine, 2016, 71(4): 135?148.

[13] WU J, LI X, Jiao L, et al. Minimum spanning trees for community detection[J]. Physica A: Statistical Mechanics and its Applications, 2013, 392(9): 2265?2277.

[14] Pirim H, Ek?io?lu B, Perkins A D. Clustering high throughput biological data with B-MST, a minimum spanning tree based heuristic[J]. Computers in Biology and Medicine, 2015, 62(7): 94?102.

[15] 李恕和, 王義章. 礦井通風(fēng)網(wǎng)絡(luò)計(jì)算的牛頓法[J]. 煤炭學(xué)報(bào), 1982(4): 52?62. LI Shuhe, WANG Yizhang. The newton method for calculating the mine ventilation networks[J]. Journal of China Coal Society, 1982(4): 52?62.

(編輯 涂鵬)

A study on minimum spanning tree algorithm of ventilation network based on weight matrix

TU Peng1, 2, ZHANG Heng1, SUN Jianchun1, WANG Lu2

(1. Key Laboratory of Transportation Tunnel Engineering, Ministry of Education, Southwest Jiaotong University, Chengdu 610031, China; 2. Sichuan Vocational and Technical College of Communications, Chengdu, 611130, China)

In order to optimize the data storage structure of the graph, narrow the search range of the minimum spanning tree construction process, improve the search efficiency and reduce the judgment in the construction process, based on weight matrices of weighted directed graph and combined properties of minimum spanning tree, a table for storing ventilation network data was proposed and partitioned. Based on the Prim algorithm and data storage structure of ventilation network, the minimum spanning tree construction method was proposed and the corresponding program was developed. In combination with the specific ventilation network structure, the process of minimum spanning tree was given in tabular form. The results show that the construction method based on weight matrix for analyzing the minimum spanning tree of an engineering example is consistent with the classical Prim algorithm. The program also proves that the method can correctly and effectively construct the minimum spanning tree of the ventilation network.

ventilation network; minimum spanning tree; Prim algorithm; weight matrix

10.19713/j.cnki.43?1423/u.2018.09.015

TD725

A

1672 ? 7029(2018)09 ? 2285 ? 08

2017?07?17

國家自然科學(xué)基金資助項(xiàng)目(51508477)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2682016CX012)

張恒(1985?)，男，貴州銅仁人，講師，博士，從事隧道及地下工程通風(fēng)與防災(zāi)研究；E?mail：tunnelzh@home.swjtu.edu.cn