C++でインシデンスリストを用いてグラフを表現するプログラムの作り方

本記事では、インシデンスリスト（incidence list）を用いてグラフを表現するC++プログラムを紹介します。このアルゴリズムの計算量はO(e)（eは辺の数）であり、辺の数に比例した時間でグラフの構成を表現できるのが特徴です。

インシデンスリストとは、グラフの各辺に対して、その辺が接続する2つの頂点を記録していくデータ構造です。「頂点を基準に隣接頂点を管理する」隣接リストとは異なり、「辺を基準に両端の頂点を管理する」点が大きな違いです。

アルゴリズム

Begin
   グラフの頂点数「v」と辺数「e」を入力として受け取る
   与えられたグラフの「e」組の頂点ペアを edge[e][2] に入力する
   各辺について、その接続に関わる対応する頂点を出力する
End

サンプルコード

#include<iostream>
using namespace std;
int main() {
   int i, v, e, j, c;
   cout<<"Enter the number of vertexes of the graph: ";
   cin>>v;
   cout<<"\nEnter the number of edges of the graph: ";
   cin>>e;
   int edge[e][2];
   for(i = 0; i < e; i++) {
      cout<<"\nEnter the vertex pair for edge "<<i+1;
      cout<<"\nV(1): ";
      cin>>edge[i][0];
      cout<<"V(2): ";
      cin>>edge[i][1];
   }
   cout<<"\n\nThe incidence list representation for the given graph: ";
   for(i = 0; i < e; i++) {
      // 各辺について、接続されている頂点を出力する
      cout<<"\n\tE("<<i+1<<") -> { ";
         cout<<"V("<<edge[i][0]<<") , "<<"V("<<edge[i][1]<<")";
         cout<<" }";
   }
}

実行結果

Enter the number of vertexes of the graph: 3
Enter the number of edges of the graph: 4
Enter the vertex pair for edge 1
V(1): 2
V(2): 1
Enter the vertex pair for edge 2
V(1): 1
V(2): 2
Enter the vertex pair for edge 3
V(1): 3
V(2): 2
Enter the vertex pair for edge 4
V(1): 2
V(2): 3
The incidence list representation for the given graph:
E(1) -> { V(2) , V(1) }
E(2) -> { V(1) , V(2) }
E(3) -> { V(3) , V(2) }
E(4) -> { V(2) , V(3) }

コードのポイントと注意点

• 計算量： 各辺を一度だけ読み込んで出力するため、全体の計算量は O(e) となります。
• 可変長配列（VLA）に注意： int edge[e][2] のように実行時にサイズを決める配列は、GCCなど一部のコンパイラでは利用できますが、C++の標準規格ではサポートされていません。移植性を重視する場合は、std::vector<std::pair<int, int>> などを利用するのがおすすめです。
• 未使用の変数： 頂点数 v は入力として受け取っていますが、処理内では直接使用されていません。入力値の妥当性チェックなどに活用すると、より堅牢なプログラムになります。

まとめ

インシデンスリストは、辺を基準にグラフの構造をシンプルに表現できる手法です。各辺の両端の頂点情報を直接扱いたい場合や、辺の列挙を頻繁に行うケースで特に有効です。本記事のサンプルコードを参考に、ぜひ自身のプログラムへ応用してみてください。