C++で隣接リストを使ってグラフを表現する方法と実装例

グラフの隣接リスト（Adjacency List）表現とは、連結リスト（リンクリスト）を用いてグラフを表す手法のことです。この表現方式では、リストの配列を使用します。配列のサイズは V であり、ここでの V はグラフの頂点数を意味します。つまり、V 個の異なるリストを格納するための配列を用意するということです。あるリストの先頭が頂点 u である場合、そのリストには u のすべての隣接頂点が格納されることを示しています。

隣接リスト表現の計算量

• この表現方式に必要な空間計算量は、無向グラフの場合 O(V+2E)、有向グラフの場合 O(V+E) となります。辺の数が増えるほど、必要な記憶領域も増加していきます。

入力：

出力：

アルゴリズム

add_edge(adj_list, u, v)

入力 − 辺 {u, v} を構成する頂点 u と v、および隣接リスト

出力 − グラフ G の隣接リスト

Begin
   インデックス u のリストに v を追加する
   インデックス v のリストに u を追加する
End

サンプルコード

#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
  for(int i = 0; i<v; i++) {
     cout << i << "--->";
     list<int> :: iterator it;
     for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
        cout << *it << " ";
     }
     cout << endl;
   }
}
void add_edge(list<int> adj_list[], int u, int v) {   // リストuにvを追加し、リストvにuを追加
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
   int v = 6;      // グラフには6つの頂点が存在する
   // サイズ6のリストの配列を作成
   list<int> adj_list[v];
   add_edge(adj_list, 0, 4);
   add_edge(adj_list, 0, 3);
   add_edge(adj_list, 1, 2);
   add_edge(adj_list, 1, 4);
   add_edge(adj_list, 1, 5);
   add_edge(adj_list, 2, 3);
   add_edge(adj_list, 2, 5);
   add_edge(adj_list, 5, 3);
   add_edge(adj_list, 5, 4);
   displayAdjList(adj_list, v);
}

実行結果

0--->4 3
1--->2 4 5
2--->1 3 5
3--->0 2 5
4--->0 1 5
5--->1 2 3 4