發(fā)布時(shí)間：2020-09-21 20:36

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

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

有向環(huán)圖Gsample

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

【參考文獻(xiàn)】

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

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

本文編號(hào)：2823961