1、圖中節(jié)點間的可達性判定,在現(xiàn)實中的多個領域有著廣泛的應用,包括知識表達、程序分析、地理導航、Internet路由、基于RDF/OWL的本體查詢、代謝網(wǎng)絡和XML索引等。
　　 一個傳統(tǒng)的解決方法是通過最短路徑算法來判定節(jié)點間的可達性,其時間復雜度是O(m),其中m=|E|(圖的邊數(shù))。對于較大的圖來說,顯然速度過慢。
　　 另一個傳統(tǒng)的解決方法是預先計算好圖中節(jié)點間是否可達,也即預先計算并存儲圖的傳遞閉包,則可在常數(shù)時間

2、內(nèi)判定可達性。然而,其空間復雜度O(n2)過大不適用于大圖,且不能有效支持圖的動態(tài)更新。
　　 其他的圖可達性判定算法還有2-HOP,HOPI和DualLabeling,但均不支持被標記圖的動態(tài)更新,且前兩種算法的時間復雜度和空間復雜度均過高,不適合應用于實際中。
　　 為有效判定圖中節(jié)點間的可達性,業(yè)已提出多種對圖可達性信息進行編碼的節(jié)點標記方案,但均無法有效地支持被標記圖的動態(tài)更新。針對這一問題,本文提出一種新的分數(shù)

3、區(qū)間標記方案(FractionalLabelingScheme,FLS)及相應的算法,并給出了相關的理論結(jié)果和實驗結(jié)果,實驗結(jié)果證明FLS能更有效地支持圖的更新并維持與原算法相當?shù)臅r空復雜度。其特點是采用分數(shù)區(qū)間對節(jié)點作標記,在保持根據(jù)判斷區(qū)間大小判斷節(jié)點間可達性的便捷性上,利用了分數(shù)區(qū)間可無限細分的特性,使得可以方便處理插入新節(jié)點的操作,圖的其它更新也只需對數(shù)據(jù)結(jié)構(gòu)進行簡單的調(diào)整,從而有效地支持圖的動態(tài)更新。
　　 圖;可達性