10日目：コンピュータ上でのグラフ構造の表現

2019年12月10日

はじめに

RCCアドカレ10日目を担当するxryuseixです．私は普段，競技プログラミング(AtCoder:xryuseix(水), Codeforces:xryuseix(青))やCTF(暗号)をやっています．そこで，今回は競技プログラミングで誰もがつまづくグラフ構造の第一歩を書きました．

グラフってなに？

例えば，あなたの街には建物が３つ(役所・図書館・学校)あります．役所から図書館までは１時間，役所から学校までは２時間かかります．この時，以下の図のように表すことができます．(画像はgenerate DOTより)

これがグラフです．この役所・図書館・学校などを頂点(ノード)といい，その二点間を結ぶ矢印を辺(エッジ)といいます．エッジとノードの関係性があり，それを図式化したものがグラフです．(厳密な話はごめんなさい><)

グラフの応用例

例えば，googlemapや電車乗換サービス，コンピュータ上のファイル構造だったりと，ありとあらゆるものがグラフ構造で表せます．よく「グラフで表せないものはない」とまで言われます．

考えかた

今回は先ほどの図で考えます．まず，コンピュータ上で使いやすくするために施設名を数字にしましょう．

役所 -> 0
図書館 -> 1
学校 -> 2

次に辺を貼りたいのですが，このような考え方をします．「0番目の施設には1番目と2番目の施設へと続く辺がある．」．他も同様に，「1番目の施設には0番目の施設へと続く辺がある．」，「2番目の施設には0番目の施設へと続く辺がある．」と考えます．一旦実装を見てみましょう．

実装方法

#include <iostream>
#include <vector>
int  main(void) {
  int n = 3; // 頂点の数
  std::vector<std::vector<int>> graph(n);
  graph[0].push_back(1); // 0番目の施設には1番目と2番目の施設へと続く辺がある．
  graph[0].push_back(2); // 同じく，0番目の要素に道の先の施設をぶら下げるイメージ
  graph[1].push_back(0);
  graph[2].push_back(0);

  // 施設0から続いている頂点を表示
  for(int i = 0; i < graph[0].size(); i++) {
    std::cout << graph[0][i] << std::endl;
  }
}