C++でグラフの隣接リストを実装する方法：サンプルコード付きで解説

グラフの隣接リストは、連結リスト（リンクリスト）を用いたグラフの表現方法の一つです。この表現では、リストを要素とする配列を使用し、その配列のサイズは V（頂点の総数）となります。言い換えれば、V個の異なるリストを格納するための配列を用意することになります。各リストの先頭が頂点 u に対応しており、そのリストには「頂点 u に隣接するすべての頂点」が格納されます。

隣接リスト表現の計算量

• 無向グラフの場合、必要な記憶領域は O(V + 2E)、有向グラフの場合は O(V + E) となります。
• 辺の数が増加すると、それに伴って必要なメモリ量も増えていきます。そのため、辺の密度が低い（スパースな）グラフに対して特に効率的な表現方法です。

入力例：

出力例：

アルゴリズム

add_edge(adj_list, u, v)

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

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

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

C++による実装例

#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;
    }
}

// 辺を追加する関数（u のリストに v を、v のリストに u を追加）
void add_edge(list<int> adj_list[], int u, int v) {
    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

このように、無向グラフの各辺について両方向の頂点を互いのリストに追加することで、隣接リストを簡単に構築できます。隣接行列と比較してメモリ使用量を抑えられるため、大規模でスパースなグラフを扱う際に隣接リストは非常に有効です。