c - cでグラフを実装するためのデータ構造のアイデア

Question

Cでグラフを実装したいのですが、各ノードをどのように保存すればよいか混乱しています。私は最初にリンクリストを使用することを考えていましたが、1つのノードに接続されている次のノードをどのように保存できますか。

どのデータ構造を使用する必要があり、どのように使用する必要があるかについてのアイデアはありますか？

Answer 1

それを行うには、いくつかのよく知られた方法があります。

1 つは、サイズ [n][n] の 2 次元配列を使用することです。ここで、n はノードの数です。a から b へのリンクがある場合は、graph[a][b]= 1 を設定します。この方法は一般に高速ですが、特にリンクやノードがそれほど多くない場合は、大量のメモリを使用します。

もう 1 つの方法は、すべてのノードのリスト (または配列) を作成し、それらすべてのコンテンツを動的配列またはリンク先のノードのリストを指すように設定することです。

Answer 2

グラフがまばらな場合に役立つデータ構造は、頂点間の接続 (エッジ) がほとんどない場合の隣接リスト(リンク リストのリンク リスト) です。

グラフが密集している場合は、隣接行列(nxn) 2 次元配列を使用します。これは、頂点間に多数のエッジがある場合です。