algorithm - グラフの隣接リスト表現

Question

スタンフォード大学のアルゴリズム コースで、教授はグラフの隣接リスト表現の次の要素を挙げました。

1. 頂点の配列またはリスト
2. エッジの配列またはリスト
3. 頂点のリスト内の各頂点は、それに付随するエッジを指します。
4. List of Edges の各エッジは、そのエッジポイントを指します。

これはウィキペディアに対応していますか? Goodrich と Tamassia によって提案されたオブジェクト指向の発生リスト構造には、頂点オブジェクトとエッジ オブジェクトの特別なクラスがありますか?

この表現は、グラフの「インシデントリスト」表現と同じですか? はいの場合、この記事で「隣接リスト」と「インシデント リスト」が分離されているのはなぜですか?

Answer 1

ノードは直接ではなくエッジを介して他のノードにリンクするため、記事の著者はその構造を発生リストと呼ぶと思います。発生リスト/隣接リストの区別は非標準であり、IMHO はあまり役に立ちません。これは、両方の構造が同様のパフォーマンス特性を持ち、リスト ADT を取り除いた場合に区別が十分に根拠があるかどうかが明確でないためです。