節(jié)點之間的可達性是圖論研究領(lǐng)域中的一個基本且重要的概念,旨在回答這樣一個問題:給出圖上的任意兩個節(jié)點u和v,是否在圖上存在至少一條從節(jié)點u到節(jié)點v,的路徑。獲得節(jié)點之間的可達性,稱為可達性查詢�？蛇_性查詢在過去的數(shù)十年中,一直是計算機科學(xué)和信息技術(shù)領(lǐng)域的重要研究課題。最早期的研究大都基于圖的傳遞閉包的概念,從理論角度提出了一些對可達性進行快速查詢的算法。隨著信息化時代的到來,基于圖模型的數(shù)據(jù)信息存儲方式的興起,可達性查詢在實際應(yīng)用中得到了高度的關(guān)注。且隨著數(shù)據(jù)信息體量的不斷增長,圖的規(guī)模也不斷增大。因此,如何快速地獲得節(jié)點之間的可達性成為了數(shù)據(jù)管理和應(yīng)用中最基本的問題之一。過去的十幾年中,眾多研究者提出了多種高效的可達性查詢算法,很大程度上解決了大規(guī)模的靜態(tài)圖上的可達性查詢問題。但是,隨著信息化時代的進一步發(fā)展,基于圖模型的數(shù)據(jù)信息越來越多地呈現(xiàn)出動態(tài)性,反映在圖上就是節(jié)點的添加與刪除,以及節(jié)點之間邊的插入與刪除。雖然可以通過多次重用已有的靜態(tài)圖上的可達性查詢算法來處理動態(tài)圖上的可達性查詢,但這并不是一種高效可行的處理方式。至此,一些研究者開始了對于動態(tài)圖上可達性查詢算法的研究。本文對動態(tài)圖上可達性查詢算法做出了深入的研究�；谝环N靜態(tài)圖上的索引類可達性查詢算法以及對有向圖任意性的考慮,提出了一種適用于任意有向圖,可處理邊的插入和刪除的動態(tài)可達性查詢算法。分析了算法的時間復(fù)雜性,并通過必要的證明,保證了算法的正確性。在此前提下,將其與現(xiàn)有的具有相同處理能力的動態(tài)可達性查詢算法進行對比實驗。在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗結(jié)果顯示,本文提出的動態(tài)可達性查詢算法總體上具有可觀的綜合優(yōu)勢。
【學(xué)位單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157.5
【部分圖文】：

查詢效率與空間需求的權(quán)衡

有向環(huán)圖Gsample

圖 2.2: dual-lableing 算法實例al-labeling 算法的可達性查詢基于這樣 條定理：節(jié)點 u 的區(qū)間節(jié)點 v 的區(qū)間標記為 [c, d)，節(jié)點 u 可以到達節(jié)點 v 當(dāng)且僅當(dāng) c

【參考文獻】

相關(guān)期刊論文 前1條

1 富麗貞;孟小峰;;大規(guī)模圖數(shù)據(jù)可達性索引技術(shù):現(xiàn)狀與展望[J];計算機研究與發(fā)展;2015年01期

本文編號：2823961