|
在圖論中，可達(dá)性是指在圖中從一個頂點到另一個頂點的容易程度。 如果存在一系列相鄰頂點，則頂點s 可以到達(dá)頂點t （并且t 可也可以到達(dá)s），以s 為開頭，以t結(jié)尾。
在無向圖中，可以通過識別圖的連接分量來確定所有頂點對之間的可達(dá)性。 當(dāng)且僅當(dāng)它們屬于同一連通分量時，這種圖中的任何一對頂點可以彼此到達(dá)。 可以在線性時間中識別無向圖的連通分量。
用于確定可達(dá)性的算法分為兩類：需要預(yù)處理的算法和不需要預(yù)處理的算法。
如果只有一個（或幾個）數(shù)據(jù)需要查詢，那么放棄使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)并直接計算可達(dá)性可能更有效。 這可以使用諸如廣度優(yōu)先搜索或迭代深化深度優(yōu)先搜索的算法在線性時間完成。[1]
如果你將查詢許多數(shù)據(jù)，那么可以使用更復(fù)雜的方法; 方法的選擇取決于被分析的圖的性質(zhì)。 作為預(yù)處理時間和一些額外存儲空間的交換，我們可以創(chuàng)建一個數(shù)據(jù)結(jié)構(gòu)，然后它可以在任何一對頂點上進(jìn)行可達(dá)性查詢。
下面概述了三種不同的算法和數(shù)據(jù)結(jié)構(gòu)。
Floyd-Warshall算法
Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd-Warshall算法的時間復(fù)雜度為O(N)，空間復(fù)雜度為O(N*N)。
Thorup 算法
對于平面有向圖，一種更快的方法是如Mikkel Thorup在2004年所提出的算法。計算復(fù)雜度為 ,其中 為增長速度非常緩慢的inverse-Ackermann函數(shù)。該算法還可以提供近似最短路徑距離以及路由 信息。 Kameda算法
如果圖形是平面的，非循環(huán)的，并且還表現(xiàn)出以下附加 屬性，則可以使用由1975年的T.Kameda 提出的更快的預(yù)處理方法：所有0-indegree和所有0-outdegree頂點出現(xiàn) （通常假設(shè)為外面），并且可以將該面的邊界分割為兩個部分，使得所有0個不等的頂點出現(xiàn)在一個部分上，并且所有的0度外的頂點出現(xiàn)在另一個部分上 （即兩種類型的頂點不交替）。 |