圖表

Question

在斯坦福的算法當然鄰接表表示，所述教授列出圖的鄰接列表表示的下列成分：

1. 數組或列表的頂點的邊
的
2. 數組或列表
3. 「頂點列表」中的每個頂點指向入射在其上的邊緣。
4. 邊緣列表中的每條邊指向其邊緣點。

這是否對應Wikipedia？ Goodrich和Tamassia提出的面向對象事件列表結構有特殊類別的頂點對象和邊緣對象？

這個表示與圖的「發生列表」表示是否相同？如果是，爲什麼在this article中認爲「鄰接列表」和「發病列表」是分開的？

Answer 1

我猜這篇文章的作者會把這個結構稱爲事件列表，因爲節點通過邊而不是直接鏈接到其他節點。事件列表/鄰接列表的區別是非標準的，恕我直言並不十分有用，因爲兩種結構都具有類似的性能特徵，並且因爲如果刪除ADT列表，這種區分是有根據的並不清楚。