リンクリスト（隣接リスト）を使ってグラフを表現するC++プログラム

グラフをコンピュータのメモリ上に格納する方法はいくつかあります。そのひとつが接続行列（インシデンス行列）です。この行列は正方行列ではなく、そのサイズは V × E となります。ここで V はグラフの頂点数、E は辺の本数を表します。

接続行列では、各行に頂点を、各列に辺を配置します。この表現では、辺 e = {u, v} に対して、列 e のうち頂点 u と頂点 v に対応する位置に 1 がマークされます。

接続行列による表現の計算量

• 接続行列による表現では、O(V × E) のメモリ領域が必要になります。完全グラフの場合、辺の本数は V(V−1)/2 となるため、接続行列はメモリを大きく消費します。

そのため、頂点数に対して辺が少ないグラフ（疎なグラフ）では、リンクリスト（隣接リスト）を用いた表現の方がメモリ効率に優れています。隣接リストでは、各頂点ごとに「隣接する頂点の一覧」をリンクリストで保持します。ここでは、C++ の std::list を使ってグラフを隣接リストで表現するプログラムを紹介します。

入力:

出力:

アルゴリズム

add_edge(adj_list, u, v)

入力 − 辺 {u, v} の頂点 u と v、および隣接リスト

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

開始
   インデックス u のリストに v を追加する
   インデックス v のリストに u を追加する
終了

サンプルコード

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

このプログラムでは、まず頂点数と同じサイズ 6 の std::list<int> 型の配列を作成します。配列の各要素がひとつの頂点に対応し、その頂点に隣接する頂点番号が格納されます。add_edge() 関数は無向グラフを扱うため、リスト u に v を、リスト v に u をそれぞれ追加します。最後に displayAdjList() 関数がすべての頂点の隣接リストを表示します。

出力

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

この実行結果から、たとえば頂点 0 には頂点 4 と 3 が隣接しており、頂点 5 には頂点 1、2、3、4 が隣接していることがわかります。隣接リストを用いることで、必要な分だけメモリを確保でき、辺の追加や隣接頂点の走査も効率的に行えます。