吳海洋

摘 要：本文基于判斷圖是否連通的Warshall算法，提出和證明了一種新的判斷無(wú)向圖的連通性的算法.

關(guān)鍵詞：鄰接矩陣；Warshall算法；連通性

中圖分類(lèi)號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1002-7661（2015）13-011-01

一、新算法的理論基礎(chǔ)

考慮到無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，并且鄰接矩陣的副上三角元素已經(jīng)包含的圖中每個(gè)點(diǎn)之間的相互關(guān)系，結(jié)合Warshall算法的思想和鄰接矩陣的副上三角元素的關(guān)系設(shè)計(jì)出一種快速判斷一個(gè)無(wú)向圖是否是連通的一種算法.根據(jù)上面的討論可以得到定理：

定理1設(shè)矩陣 是無(wú)向圖 的鄰接矩陣， 是矩陣A的副上三角矩陣，如果 的副上三角元素都是非零的，那么圖 是連通的，否則是非連通的，其中n是圖G節(jié)點(diǎn)數(shù)目.

證明：由（引理1）知：圖 連通的充分必要條件是矩陣 中的所有的元素非零，其中C是圖 的鄰接矩陣.計(jì) ，其中 . 的值表示從節(jié)點(diǎn) 出發(fā)經(jīng)過(guò) 步到達(dá) 的路徑數(shù)目。如果 為零表示不存在這樣的路徑。由此可知如果 非零，則 可達(dá)

1、現(xiàn)在考慮C的副上三角矩陣 ，如果 的副上三角元素非零，即所有的 根據(jù)（1）知 可達(dá) ，.遍歷副上三角的所有元素以及無(wú)向圖鄰接矩陣的的對(duì)稱(chēng)性可得，圖G是連通的.反之如果 可達(dá) ，則有 證畢.

二、新算法設(shè)計(jì)

現(xiàn)在根據(jù)定理1來(lái)設(shè)計(jì)一個(gè)判斷無(wú)向圖是否連通的新算法，步驟如下：

步驟1：輸入圖G的鄰接矩陣 ；

步驟2：計(jì)算出A的副上三角矩陣 ；

步驟3：計(jì)算出 的副上三角元素；

步驟4：S的所有副上三角元素非零，則圖G是連通的，輸出1，否則是非連通的，輸出0；

將上述的算法命名為：判斷無(wú)向圖連通性的快速Warshall算法.

三、兩種算法的時(shí)間復(fù)雜度與空間復(fù)雜度的比較

1、時(shí)間復(fù)雜度的比較

現(xiàn)在假設(shè)鄰接矩陣是 的階數(shù)是 ，Warshall算法是對(duì)鄰接矩陣進(jìn)行矩陣乘法的運(yùn)算，根據(jù)相關(guān)的數(shù)學(xué)知識(shí)，需要做乘法運(yùn)算的次是：

…..（2）

以及做加法的次數(shù)是： .

而新算法做乘法的次數(shù) .（3）

現(xiàn)在對(duì)式（2）和式（3）做比值并取極限 ……………（4）

從式（4）中不難發(fā)現(xiàn)改進(jìn)后的算法的的效率較原算法效率更高，時(shí)間復(fù)雜度更低，效率大約是原來(lái)的4倍。

2、空間復(fù)雜度的比較

從計(jì)算機(jī)內(nèi)存存放矩陣的角度來(lái)看，判斷圖連通性的快速Warshall算法只需要存儲(chǔ)有用數(shù)據(jù)，即矩陣的副上三角元素.較Warshall算法存儲(chǔ)的空間減少了一半以上.

四、結(jié)論

從上面的分析可以看出改進(jìn)后的方法速度更快，計(jì)算時(shí)占用的內(nèi)存更少！更符合大規(guī)模的運(yùn)算，從而在計(jì)算網(wǎng)絡(luò)的連通度以及系統(tǒng)網(wǎng)絡(luò)可靠性方面更加快捷。

參考文獻(xiàn)：

[1] 耿素云.屈婉玲.張立昂.離散數(shù)學(xué)[M].北京：清華大學(xué)出版社，2005：88—92[2]