幅優先探索とは

幅優先探索(Breadth first search) はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられる。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。

幅優先探索 – Wikipediaより

実装

幅優先探索をC++で実装してみる。

#include <vector>
#include <queue>
#include <iostream>

using namespace std; 

int n = 6;

void setGraph(vector<vector<char> > &map, int x, int y) {
  map[y][x] = 1;
  map[x][y] = 1;
}

vector<vector<char> > readMap() {
  vector<vector<char> > map(n, vector<char>(n));
  setGraph(map, 0, 1);
  setGraph(map, 0, 2);
  setGraph(map, 1, 3);
  setGraph(map, 2, 3);
  setGraph(map, 3, 4);
  setGraph(map, 3, 5);
  return map;
}

int main(void) {
  vector<vector<char> > map = readMap();
  vector<int> distance(n), preview(n);
  vector<bool> visited(n);

  for (int i = 0; i < n; i++) {
    visited[i] = false;
    distance[i] = 0;
  }

  queue<int> q;
  int START = 0;
  q.push(START);
  visited[START] = true;
  while (!q.empty()) {
    int i = q.front();
    q.pop();

    for (int j = 0; j < n; j++) {
     if (map[i][j] == 1 && visited[j] == false) {
      distance[j] = distance[i] + 1;
      visited[j] = true;
      preview[j] = i;
      q.push(j);
     }
    }
  }

  cout << "point" << " preview" << " distance" << endl;
  for (int i = 0; i < n; i++) {
    cout << i + 1 << "    " << preview[i] + 1 << "     " << distance[i] << endl;
  }
  return 0;
}

実行結果

point preview distance
1     1       0
2     1       1
3     1       1
4     2       2
5     4       3
6     4       3

関連リンク

• 幅優先探索 – Wikipedia

Tweet

そこに3つのボタンがあるじゃろ？
どれでも好きなものを押していくといい。