一種判定的無向圖連通性的快速Warshall算法

吳海洋

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

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

中圖分類號：G642 文獻標(biāo)識碼：B 文章編號：1002-7661（2015）13-011-01

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

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

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

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

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

二、新算法設(shè)計

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

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

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

步驟3：計算出 的副上三角元素；

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

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

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

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

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

…..（2）

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

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

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

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

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

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

四、結(jié)論

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

參考文獻：

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