C++ グラフ・探索

参考サイト

DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【前編】 - Qiita

グラフを隣接リストで表す

隣接リストは、各頂点毎に、隣接する頂点の配列を作ります。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

int main()
{
  Graph G;
  G.at(0) = {1, 2};
  G.at(1) = {0, 2, 3};
  G.at(2) = {0, 1, 4};
  G.at(3) = {1, 4, 5};
  G.at(4) = {2, 3, 6};
  G.at(5) = {3};
  G.at(6) = {4};
}

0と1はお互いがお互いを配列に入れてるので、これは無向グラフ。有効グラフの場合はどちらかに入る。

BFS（幅優先探索）

サンプルコード

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

Graph G(7);
vector<bool> seen;
vector<int>  todo;

void bfs()
{
  while(todo.size() > 0)
  {
    // todoからFIFOでvを取り出す
    int v = todo.at(0);
    todo.erase(todo.begin());

    cout <<  v << ' ';
    for (int next_v : G.at(v))
    {
      if (seen.at(next_v)) continue;
      seen.at(next_v) = true;
      todo.push_back(next_v);
    }
  }
}

int main()
{
  G.at(0) = {1, 2};
  G.at(1) = {0, 2, 3};
  G.at(2) = {0, 1, 4};
  G.at(3) = {1, 4, 5};
  G.at(4) = {2, 3, 6};
  G.at(5) = {3};
  G.at(6) = {4};

  seen.assign(7, false);
  seen.at(0) = true;
  todo.push_back(0);
  bfs();
}

結果

0 1 2 3 4 5 6

DFS（深さ優先探索）

上記のBFSのコードの下記部分を変更する。

変更前（BFS）

// todoからFIFOでvを取り出す
int v = todo.at(0);
todo.erase(todo.begin());

変更後（DFS）

// todoからLIFOでvを取り出す
int v = todo.at(todo.size() - 1);
todo.pop_back();

サンプルコード

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

Graph G(7);
vector<bool> seen;
vector<int>  todo;

void dfs()
{
  while(todo.size() > 0)
  {
    // todoからLIFOでvを取り出す
    int v = todo.at(todo.size() - 1);
    todo.pop_back();

    cout <<  v << ' ';
    for (int next_v : G.at(v))
    {
      if (seen.at(next_v)) continue;
      seen.at(next_v) = true;
      todo.push_back(next_v);
    }
  }
}

int main()
{
  G.at(0) = {1, 2};
  G.at(1) = {0, 2, 3};
  G.at(2) = {0, 1, 4};
  G.at(3) = {1, 4, 5};
  G.at(4) = {2, 3, 6};
  G.at(5) = {3};
  G.at(6) = {4};

  seen.assign(7, false);
  seen.at(0) = true;
  todo.push_back(0);
  dfs();
}

結果

0 2 4 6 3 5 1

DFS（再帰を使う場合）

サンプルコード

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void dfs(const Graph &G, vector<bool> &seen, int v)
{
  cout << v << ' ';
  seen.at(v) = true;
  for (auto next_v : G.at(v))
  {
    if (seen.at(next_v)) continue;
    dfs(G, seen, next_v);
  }
}

int main()
{
  Graph G(7);
  G.at(0) = {1, 2};
  G.at(1) = {0, 2, 3};
  G.at(2) = {0, 1, 4};
  G.at(3) = {1, 4, 5};
  G.at(4) = {2, 3, 6};
  G.at(5) = {3};
  G.at(6) = {4};

  vector<bool> seen(G.size(), false);
  dfs(G, seen, 0);
}