適用于稀疏圖的基于關(guān)鍵點(diǎn)標(biāo)記的可達(dá)性算法

摘要： 有向圖中任意兩點(diǎn)間的可達(dá)性查詢是研究各種網(wǎng)絡(luò)問題時(shí)的一個(gè)基礎(chǔ)操作，如在社交網(wǎng)絡(luò)中查詢兩個(gè)人是否相互關(guān)注等。但隨著網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大，傳統(tǒng)算法因巨大的時(shí)間或空間復(fù)雜度而變得難以被應(yīng)用。因此需要根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)針對性地使用合適的可達(dá)性算法。稀疏圖可以看作由若干有向生成樹與少量非樹邊組成，GRKPL算法將稀疏圖中的可達(dá)性問題拆分成兩部分：樹上可達(dá)性問題與加入非樹邊后帶來的影響。前一部...