[科普中國(guó)]-可達(dá)性

簡(jiǎn)介

在圖論中，可達(dá)性是指在圖中從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的容易程度。 如果存在一系列相鄰頂點(diǎn)，則頂點(diǎn)s 可以到達(dá)頂點(diǎn)t （并且t 可也可以到達(dá)s），以s 為開(kāi)頭，以t結(jié)尾。

在無(wú)向圖中，可以通過(guò)識(shí)別圖的連接分量來(lái)確定所有頂點(diǎn)對(duì)之間的可達(dá)性。 當(dāng)且僅當(dāng)它們屬于同一連通分量時(shí)，這種圖中的任何一對(duì)頂點(diǎn)可以彼此到達(dá)。 可以在線性時(shí)間中識(shí)別無(wú)向圖的連通分量。

算法用于確定可達(dá)性的算法分為兩類(lèi)：需要預(yù)處理的算法和不需要預(yù)處理的算法。

如果只有一個(gè)（或幾個(gè)）數(shù)據(jù)需要查詢(xún)，那么放棄使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)并直接計(jì)算可達(dá)性可能更有效。 這可以使用諸如廣度優(yōu)先搜索或迭代深化深度優(yōu)先搜索的算法在線性時(shí)間完成。1

如果你將查詢(xún)?cè)S多數(shù)據(jù)，那么可以使用更復(fù)雜的方法; 方法的選擇取決于被分析的圖的性質(zhì)。 作為預(yù)處理時(shí)間和一些額外存儲(chǔ)空間的交換，我們可以創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)，然后它可以在任何一對(duì)頂點(diǎn)上進(jìn)行可達(dá)性查詢(xún)。

下面概述了三種不同的算法和數(shù)據(jù)結(jié)構(gòu)。

Floyd-Warshall算法Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N*N)。

Thorup 算法對(duì)于平面有向圖，一種更快的方法是如Mikkel Thorup在2004年所提出的算法。計(jì)算復(fù)雜度為 ,其中為增長(zhǎng)速度非常緩慢的inverse-Ackermann函數(shù)。該算法還可以提供近似最短路徑距離以及路由信息。

Kameda算法如果圖形是平面的，非循環(huán)的，并且還表現(xiàn)出以下附加屬性，則可以使用由1975年的T.Kameda 提出的更快的預(yù)處理方法：所有0-indegree和所有0-outdegree頂點(diǎn)出現(xiàn) （通常假設(shè)為外面），并且可以將該面的邊界分割為兩個(gè)部分，使得所有0個(gè)不等的頂點(diǎn)出現(xiàn)在一個(gè)部分上，并且所有的0度外的頂點(diǎn)出現(xiàn)在另一個(gè)部分上 （即兩種類(lèi)型的頂點(diǎn)不交替）。

相關(guān)問(wèn)題一個(gè)相關(guān)的問(wèn)題是解決具有一些數(shù)目k的頂點(diǎn)失敗的可達(dá)性查詢(xún)。類(lèi)似的問(wèn)題可以考慮邊緣故障而不是頂點(diǎn)故障，或者兩者的混合。 廣度優(yōu)先搜索技術(shù)在這樣的查詢(xún)上也同樣有效。2

與可達(dá)性查詢(xún)相關(guān)的另一個(gè)問(wèn)題是當(dāng)圖的某些部分改變時(shí)，快速重新計(jì)算可達(dá)性關(guān)系的改變。