グラフの基本的な内容です。グラフが隣接リストの形で与えられたとき、隣接行列に直します。

隣接リストと隣接行列

隣接リスト

配列Aを用意します。頂点uに対して、A[u]はuと隣接する全ての頂点を格納します。

隣接行列

２次元配列Aを用意します。頂点iから頂点jへリンクがある場合は $a_{ij} = 1$ となり、ない場合は0となります。無向グラフであれば隣接行列は対称行列となります。

隣接行列は要素へのアクセスは定数時間と高速ですが、全てのノード間の関係について記録するので、疎なグラフではメモリが無駄になってしまいます。

実装

次の問題を解いてみます。

グラフの表現 | アルゴリズムとデータ構造 | Aizu Online Judge

解答例：

#include<iostream>
using namespace std;

#define N 100

int main() {
  int i, j, n, u, k, v;
  int A[N+1][N+1];  // 隣接行列

  cin >> n;
    
  // 初期化
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      A[i][j] =  0;
    }
  }    

  // 隣接行列表現に直す
  for (i = 0; i < n; i++) {
    cin >> u >> k;
    for (j = 0; j < k; j++) {
      cin >> v;
      A[u][v] = 1;
    }
  }

  // 出力
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      if (j > 1) cout << " ";
      cout << A[i][j];
    }
    cout << endl;
  }

  return 0;
}