在圖論中，可達性是指在圖中從一個頂點到另一個頂點的容易程度。在無向圖中，可以通過識別圖的連線分量來確定所有頂點對之間的可達性。 常用算法為：Floyd-Warshall,Thorup,Kameda這三種算法。
基本介紹
- 中文名：可達性
- 外文名：Reachability
- 解釋：一個地方到另一個地方的容易程度
- 算法：Floyd-Warshall,Thorup,Kameda
基本介紹,算法,相關問題,
基本介紹
在圖論中，可達性是指在圖中從一個頂點到另一個頂點的容易程度。 如果存在一系列相鄰頂點，則頂點s 可以到達頂點t （並且t 可也可以到達s），以s 為開頭，以t結尾。
在無向圖中，可以通過識別圖的連線分量來確定所有頂點對之間的可達性。 若且唯若它們屬於同一連通分量時，這種圖中的任何一對頂點可以彼此到達。 可以線上性時間中識別無向圖的連通分量。
算法
用於確定可達性的算法分為兩類：需要預處理的算法和不需要預處理的算法。
如果你將查詢許多數據，那么可以使用更複雜的方法; 方法的選擇取決於被分析的圖的性質。 作為預處理時間和一些額外存儲空間的交換，我們可以創建一個數據結構，然後它可以在任何一對頂點上進行可達性查詢。
下面概述了三種不同的算法和數據結構。
Floyd-Warshall算法
Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。Floyd-Warshall算法的時間複雜度為O(N)，空間複雜度為O(N*N)。
Thorup 算法
對於平面有向圖，一種更快的方法是如Mikkel Thorup在2004年所提出的算法。計算複雜度為
,其中
為增長速度非常緩慢的inverse-Ackermann函式。該算法還可以提供近似最短路徑距離以及路由信息。
Kameda算法
如果圖形是平面的，非循環的，並且還表現出以下附加屬性，則可以使用由1975年的T.Kameda 提出的更快的預處理方法：所有0-indegree和所有0-outdegree頂點出現 （通常假設為外面），並且可以將該面的邊界分割為兩個部分，使得所有0個不等的頂點出現在一個部分上，並且所有的0度外的頂點出現在另一個部分上 （即兩種類型的頂點不交替）。
相關問題
一個相關的問題是解決具有一些數目k的頂點失敗的可達性查詢。類似的問題可以考慮邊緣故障而不是頂點故障，或者兩者的混合。 廣度優先搜尋技術在這樣的查詢上也同樣有效。
與可達性查詢相關的另一個問題是當圖的某些部分改變時，快速重新計算可達性關係的改變。
