グラフ・最短距離アルゴリズムのまとめメモ（１）

序文

自分の頭の中で纏まらなくてブログで復習を兼ねて書きたいと思います。 そしていろいろと調べたりして基本以外にもある良いアルゴリズムも纏めて書こうしました。

参照

INTRODUCTIONS TO ALGORITHMS 3rd EDITION Chapter 22

幅優先探索 - Wikipedia

深さ優先探索 - Wikipedia

---

本文

1. BFS（幅優先探索）

• 一番単純な探索アルゴリズム。しかしDijkstra、Primの元となるアルゴリズムである。
• グラフとスターティングポイント（Source）を根ノードとし到達できる全ての任意位置を探して距離を計算する。
• からの距離がであるノードを探索する前に、のノードを全て探索する。BFSという名はグラフでの探索した領域を広めるということで名付けられた。
• BFS自体はヒューリスティックを使っていないため、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
• BFSはDirected、Indirected全てのグラフに適用できる。
• BFSによって生成されたツリーの形は一つに限られている。
• BFSは最適である。

More deep inside

• BFSを実装するときに、各ノードに対して状態は3つを持つ。
  1. 白：まだ探索されていない場合。
  2. グレー：白から変わり、後の探索の為にQueueに入っている場合。
  3. 黒：探索済み。BFSは全てのノードが一度しか発見されない。
• 各ノードに対して一度しか発見されないため、各ノードの親ノードは最大一個まで持つ。
• ノードの状態が【黒】なら隣接する全てのノードは【白】ではない。
• Queueに入っているノードの状態はいつも【グレー】である。
• BFSの時間複雑度はだ。何故ならはグラフの全てのノードをQueueに入れることによって、そしては任意ノードにて隣接するノードを探索する時に繋がる辺の総合がだからだ。

コード

void BFS(TMazeContainer &map) {
  auto &start = map[0][0];  start.dist_from_start = 0;
  std::queue<SNode*> queue; queue.push(&start);

  while (!queue.empty()) {
    auto present = queue.front();

    for (auto dir = 0; dir < 4; ++dir) {
      auto &neighbor = present->neighbors[dir];
      if (neighbor.node == nullptr) { continue; }
      if (neighbor.node->status == ENodeStatus::Stay) { continue; }

      auto next = neighbor.node;
      if (next->status == ENodeStatus::Idle) {
        next->status = ENodeStatus::Stay;
        next->dist_from_start = present->dist_from_start + 1;
        next->parent = present;

        switch (static_cast<EDirection>(dir))
        {
        default: break;
        case EDirection::Up:    next->parent_dir = EDirection::Down;  break;
        case EDirection::Down:  next->parent_dir = EDirection::Up;    break;
        case EDirection::Left:  next->parent_dir = EDirection::Right; break;
        case EDirection::Right: next->parent_dir = EDirection::Left;  break;
        }

        queue.push(next);
      }
    }

    present->status = ENodeStatus::Visited;
    queue.pop();
  }
}

2. DFS（深さ優先探索）

• BFSとは違ってDFSはノードから可能な限り深く検索することを目指している。
• グラフから一番最近に発見して、まだ調査されていない辺を持つノードからスタックや再帰を活用して最後まで探索する。
• から派生した全ての辺が調査したら、ノードを発見してくれたノードに隣接する他のノードを調査するためにスタックを巻き戻す。
• BFSとは違って、スターティングポイントが複数存在しうる。何故ならDFSは最短距離を測るためのアルゴリズムとして使用するのではなく一般的には別のアルゴリズムのサブルーチンとして活用するからだ。（BFSは上記でもあるように最短距離によく使われる）
• DFSは最適ではない。完全でもない。
• DFSはトポロジカルソートに使用される。

More deep inside

• DFSを実装するときに、各ノードに対して状態は3つを持つ。
  1. 白：まだ探索されていない場合。
  2. グレー：辺のよって発見されてStackに入っていてから、ついに探索の対象となったとき変わる。
  3. 黒：隣接した辺による再帰が終わってから探索済みになる時、変わる。
• 各ノードに対して一度しか探索対象とされないため、各ノードの親ノードは最大一個まで持つ。
• そしてDFSは残されたノードに対して任意位置のノード（白）からまたDFSを行えるので親へのグラフが一つより多くなる場合もある。なのでDFSで構築された深さ優先ツリーはフォレスト（Forest）を形成する。（predecessor subgraph）
• DFSの時間複雑度はだ。

タイムスタンプ

Introduction To Algorithm 3ed p620 fig 22.5

• DFSは探索する時に時間を記録する。そして各ノードは2つの時間記録を持つ。一つ目はノードが最初に探索対象となった時に、二つ目は対象となるノードに隣接する辺による再帰探索が終わった後に記す。これによってグラフの構造に重要な情報をもたらすらしい。

コード

auto sTime = 0u;

void DFS_Internal(TMazeContainer& map, SNode& cursor);
void DFS(TMazeContainer& map) {
  sTime = 0u;
  for (auto& xList : map) { // Y
    for (auto& element : xList) { // X
      // FIND ANY WHITE NODE
      if (element.status == ENodeStatus::Idle) { 
        element.dist_from_start = 0;
        DFS_Internal(map, element);
      }
    }
  }
}

void DFS_Internal(TMazeContainer& map, SNode& cursor) {
  cursor.status = ENodeStatus::Stay;
  sTime += 1; cursor.timestamp.startSearch = sTime;

  for (auto dir = 0; dir < 4; ++dir) {
    auto &neighbor = cursor.neighbors[dir];
    if (neighbor.node == nullptr)                   { continue; }
    if (neighbor.node->status != ENodeStatus::Idle) { continue; }

    auto *next = neighbor.node;
    next->dist_from_start = cursor.dist_from_start + 1;
    next->parent = &cursor;
    neighbor.is_traversed = true;

    switch (static_cast<EDirection>(dir)) {
    default: break;
    case EDirection::Up:    next->parent_dir = EDirection::Down;  break;
    case EDirection::Down:  next->parent_dir = EDirection::Up;    break;
    case EDirection::Left:  next->parent_dir = EDirection::Right; break;
    case EDirection::Right: next->parent_dir = EDirection::Left;  break;
    }
    DFS_Internal(map, *next);
  }
  sTime += 1; cursor.timestamp.endSearch = sTime;
}

---

結論

一つでまとめようとしましたけど出来ませんでした。
肝心のDijkstra、Bellman-ford、A*、そしてもっと高級のアルゴリズムは（２）にて書きます。