c - C プログラミング言語 グラフの構造

Question

グラフ構造の構築に問題があります。単純にリンクされたリストを作成する方法と、二重に作成する方法も知っています。しかし、このサイトのようなグラフ構造を構築したい (pic.output) http://www.cs.sunysb.edu/~algorith/files/graph-data-structures.shtml

Answer 1

次の 3 つの一般的な解決策があります。

• 隣接行列 ( N*NN が頂点の数である行列を格納し、エッジが にあるmatrix[x][y]場合は値を格納し、それ以外の場合は 0を格納します)xy
• エッジ リストでは、エッジの長いリストを保持するだけで、カップル(x,y)がリストに含まれている場合、x から y へのエッジが存在します。
• 隣接リスト。頂点のリストがあり、すべての頂点xには x がエッジを持つノードへのエッジのリストがあります。

すべての異なるアプローチは、

• 必要なスペース
• 他の操作よりも特定の操作に関連する計算の複雑さ

したがって、グラフで何をする必要があるかに応じて、それらのいずれかを選択できます。上記の可能な実装の特定の特徴を知りたい場合は、別の SO の質問に対する私の回答をご覧ください。