我們可以把萬維網看成壹個節點,網頁之間的超鏈接看成壹個由邊組成的圖。同時,我們可以假設:
以上述方式將萬維網概念化為圖之後,讓我們來看看流行的搜索引擎是如何使用它的。例如,谷歌使用爬蟲來索引網頁。這些爬蟲首先通過橫向遍歷訪問鏈接來瀏覽網頁。還有很多其他可以這樣遍歷的圖的例子,比如:科研論文之間的引用圖,我們在寫論文的時候參考;百科全書中的參考文獻。
2000年,AltaVista的創始人進行了壹項實驗【網絡中的圖形結構——科學直達】。
]來探索網絡的形態。論文拋出壹個問題:給定壹個節點,這個節點可以到達哪些節點;還有哪些節點可以訪問該節點?
這將產生兩種類型的節點:
運行壹個簡單的BFS就可以遍歷上述兩組。比如下圖。
有兩種類型的有向圖:
任何有向圖都可以表示為這兩種類型的組合,可以通過以下兩步實現:
* *從有向圖獲得強連通圖* *
將SCC合並到超級節點中,並創建壹個新的圖G '