コンピュータ上で単純な無向グラフを表現するには、さまざまな方法があります。
- 隣接リスト: 頂点はレコードまたはオブジェクトとして格納され、すべての頂点は隣接する頂点のリストを格納します。このデータ構造により、頂点に追加のデータを格納できます。
- インシデント リスト: 頂点とエッジは、レコードまたはオブジェクトとして保存されます。各頂点はそのインシデント エッジを格納し、各エッジはそのインシデント頂点を格納します。このデータ構造により、頂点とエッジに追加のデータを格納できます。
- 隣接行列: 行がソース頂点を表し、列が宛先頂点を表す 2 次元マトリックス。エッジと頂点のデータは外部に保存する必要があります。頂点の各ペア間に格納できるのは、1 つのエッジのコストだけです。
- 入射行列: 2 次元のブール行列で、行が頂点を表し、列がエッジを表します。エントリは、行の頂点が列のエッジに付随しているかどうかを示します。
2 つの質問:
- ある表現から別の表現に移行するための効率的なアルゴリズムは何ですか?
- ある表現から別の表現に移行する際の複雑さは何ですか?