基于區(qū)間擴展的可達性查詢算法研究.pdf

1、給定有向無環(huán)圖G，以及圖上的任意兩點u、v。回答u是否能夠到達v的可達性查詢是圖的基本操作之一。隨著現(xiàn)代化信息技術的快速發(fā)展，圖被廣泛應用于生物學、社交網絡、語義網絡、模式識別等領域，圖的可達性查詢是圖數據管理中的熱點問題之一。大量的學者投入精力改進可達性查詢算法的效率。但是已存在的可達性查詢算法，由于索引占用空間太大、查詢效率低下等原因，在面對規(guī)模不斷增長的數據圖時，效率低、擴展性差。本文從以下幾個方面對可達性查詢問題進行研究。

2、>　　首先，分析現(xiàn)有可達性查詢問題，發(fā)現(xiàn)已有算法構建索引時間長，索引占用空間大，查詢效率低下。
　　其次，本文提出線性時間復雜度的索引構建算法，在拓撲排序的過程中，為每個結點指定相應的索引標簽，包含一對互逆的拓撲序號和該結點在生成樹上的區(qū)間。提出壓縮的索引表示方式，索引的空間復雜度為 O(n)。提出基于孩子結點的區(qū)間擴展策略，對于要擴展的結點u，將其用于覆蓋生成樹上孩子的區(qū)間擴展到圖中覆蓋出鄰居結點的區(qū)間，增強了回答肯定性可達查詢