圖邊查詢

Question

歸屬圖最常見的表現形式是鄰接​​矩陣或列表，其中節點被視爲第一類公民。有許多圖表查詢，如鄰居，最短路徑，頁面排名，在這些矩陣上運行的連接組件以及節點上的列表結構。節點/邊的屬性也可以與連接分開存儲。

該圖的另一種表示形式是incidence matrix，其中節點的入射邊緣被記錄在矩陣中。我知道它們表示與以前基於節點的方法完全相同的信息。

我的問題是，是否有任何圖表查詢/工作量/算法可以從關聯矩陣結構中受益，而不是使用基於節點的結構，即有利於基於邊緣的結構？當使用關鍵矩陣時呢？

Answer 1

我能想到只有一例的其中關聯矩陣可能證明更快：

查找節點的度或找到相鄰的節點是使用鄰接矩陣和O時是具有複雜度O（V）的操作（E ）當使用關聯矩陣時。

通常E> V，但如果圖有很多0度節點，情況可能不是這樣。由於找到相鄰節點是一項基本操作，因此許多算法在這些圖上可能會更快。