4th term 6th week - dsuz/csharp GitHub Wiki
- 幅優先探索 (Breadth First Search, BFS)
用語の説明等は前回を参照してください。また適宜、深さ優先探索と比較するため、前回学んだ「深さ優先探索」を知っていることを前提とします。
深さ優先探索では、スタックと再起呼び出しを使った。一方、幅優先探索では、キューとループを使って探索する。
幅優先探索では、スタート地点から領域を広げるようにして探索を行う。例えば次のグラフで頂点０からスタートして頂点３をゴールとする場合、以下のように探索する。
これをプログラミングで求めたい時、深さ優先探索の時と同様、以下の情報が必要になる。
- 頂点数
- スタートする頂点
- ゴールとなる頂点
- 隣接情報
隣接情報については前回を参照してください。
前項で必要と述べた、頂点数、スタートする頂点、ゴールとなる頂点、隣接情報は、データとしては次のように与えられる。
コピペ用にテキストのデータも示しておく。
6 0 3 6
0 1
1 2
1 4
1 5
2 5
3 5
アルゴリズム（手順）としては次のようになる。
- キューに現在いる頂点を追加する
- キューの先頭から頂点を１つ取り出す
- 取り出した頂点がゴールだったら、探索は終了する
- 取り出した頂点の隣接頂点のうち、未訪問の頂点をすべてキューに追加する
- キューが空でない場合は、2. に戻る
- ゴールに到達せずにキューが空になった場合は、ゴールには到達できない
using System;
using System.Collections.Generic; // Queue<> のため
class Program
{
static void Main(string[] args)
{
var prms = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int n = prms[0], start = prms[1], goal = prms[2], rowCount = prms[3]; // n: 頂点数, rowCount: 読み込む隣接情報の行数
var adj = new bool[n, n]; // 隣接 (adjacent) 情報を入れる行列
var visitedNodes = new bool[n]; // 訪問済み頂点
for (int i = 0; i < rowCount; i++)
{
var edges = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
adj[edges[0], edges[1]] = true;
adj[edges[1], edges[0]] = true; // 双方向に移動可能なので、0 -> 1 も移動できるし 1 -> 0 も移動できる
} // 隣接情報を読み込む
var q = new Queue<int>();
q.Enqueue(start); // スタート地点を入れる
visitedNodes[start] = true; // スタート地点は訪問済みにする
while (q.Count > 0)
{
var currentNode = q.Dequeue();
if (currentNode == goal)
{
Console.WriteLine("GOAL!!!");
return;
} // ゴールに着いたか調べる
for (int i = 0; i < n; i++)
{
var nextNode = i; // 移動先頂点の候補
if (!visitedNodes[nextNode] && adj[currentNode, nextNode])
{
q.Enqueue(nextNode);
visitedNodes[nextNode] = true;
Console.WriteLine($"{currentNode} -> {nextNode}"); // 移動した辺を出力する
}
} // nextNode が移動可能かつ未訪問である場合は次の探索候補としてキューに入れる
} // キューが空になるまで探索する
Console.WriteLine("Unreachable goal."); // ゴールにたどり着けなかった
}
}ただし、上のコードでは「ゴールに到着できるか、できないか」しか調べることができない。そこで次のプログラムでは「ゴールまで最短で何回の移動でたどり着けるか」を調べる。
using System;
using System.Collections.Generic; // Queue<> のため
using System.Linq; // Enumerable.Repeat() のため
class Program
{
static void Main(string[] args)
{
var prms = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int n = prms[0], start = prms[1], goal = prms[2], rowCount = prms[3]; // n: 頂点数, rowCount: 読み込む隣接情報の行数
var adj = new bool[n, n]; // 隣接 (adjacent) 情報を入れる行列
var visitedNodes = Enumerable.Repeat(-1, n).ToArray(); // 訪問済み頂点に何回の移動でたどり着けたか（負の値が入っている場合は未訪問）
for (int i = 0; i < rowCount; i++)
{
var edges = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
adj[edges[0], edges[1]] = true;
adj[edges[1], edges[0]] = true; // 双方向に移動可能なので、0 -> 1 も移動できるし 1 -> 0 も移動できる
} // 隣接情報を読み込む
var q = new Queue<int>();
q.Enqueue(start); // スタート地点を入れる
visitedNodes[start] = 0; // スタート地点は訪問済みにする
while (q.Count > 0)
{
var currentNode = q.Dequeue();
if (currentNode == goal)
{
Console.WriteLine($"You need {visitedNodes[currentNode]} steps to goal.");
return;
} // ゴールに着いたか調べる
for (int i = 0; i < n; i++)
{
var nextNode = i; // 移動先頂点の候補
if (visitedNodes[nextNode] < 0 && adj[currentNode, nextNode])
{
q.Enqueue(nextNode); // 次の探索候補としてキューに入れる
visitedNodes[nextNode] = visitedNodes[currentNode] + 1; // 何回目の移動で訪問できたか記録する
Console.WriteLine($"Step {visitedNodes[nextNode]}: {currentNode} -> {nextNode}"); // 移動した辺と、そこまでの移動回数を出力する
}
} // nextNode が移動可能かつ未訪問である場合は次の探索候補としてキューに入れる
} // キューが空になるまで探索する
Console.WriteLine("Unreachable goal."); // ゴールにたどり着けなかった
}
}最短経路を求めたい場合は、次のコードのように経路を復元する必要がある。経路の復元方法はこちらのやり方を使っている。
using System;
using System.Collections.Generic; // Queue<> のため
using System.Linq; // Enumerable.Repeat() のため
class Program
{
static void Main(string[] args)
{
var prms = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int n = prms[0], start = prms[1], goal = prms[2], rowCount = prms[3]; // n: 頂点数, rowCount: 読み込む隣接情報の行数
var adj = new bool[n, n]; // 隣接 (adjacent) 情報を入れる行列
var visitedNodes = Enumerable.Repeat(-1, n).ToArray(); // 訪問済み頂点にどの頂点から移動してきたか（負の値が入っている場合は未訪問）
var isGoal = false; // ゴールにたどり着いたか
for (int i = 0; i < rowCount; i++)
{
var edges = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
adj[edges[0], edges[1]] = true;
adj[edges[1], edges[0]] = true; // 双方向に移動可能なので、0 -> 1 も移動できるし 1 -> 0 も移動できる
} // 隣接情報を読み込む
var q = new Queue<int>();
q.Enqueue(start); // スタート地点を入れる
visitedNodes[start] = 0; // スタート地点は訪問済みにする
while (q.Count > 0)
{
var currentNode = q.Dequeue();
if (currentNode == goal)
{
isGoal = true;
break;
} // ゴールに着いたか調べる
for (int i = 0; i < n; i++)
{
var nextNode = i; // 移動先頂点の候補
if (visitedNodes[nextNode] < 0 && adj[currentNode, nextNode])
{
q.Enqueue(nextNode); // 次の探索候補としてキューに入れる
visitedNodes[nextNode] = currentNode; // どの頂点から移動してきたか記録する
Console.WriteLine($"{currentNode} -> {nextNode}"); // 移動した辺と、そこまでの移動回数を出力する
}
} // nextNode が移動可能かつ未訪問である場合は次の探索候補としてキューに入れる
} // キューが空になるまで探索する
if (isGoal)
{
// ゴールから逆にたどって経路を復元する
var route = new Stack<int>();
route.Push(goal);
while (true)
{
var node = route.Pop();
route.Push(node);
var lastNode = visitedNodes[node]; // node への移動元（直前のノード）
route.Push(lastNode);
if (lastNode == start)
{
Console.WriteLine(string.Join("->", route));
break;
}
}
} // ゴールに到着した場合は、経路を復元して出力する
else
{
Console.WriteLine("Unreachable goal."); // ゴールにはたどり着けなかった
}
}
}以下の特徴は必ず抑えておきましょう。
- ループとキューを使う
- ゴールまでの最短経路を探索するが、経路を求めたければ復元する必要がある
以下の問題を解いてみましょう。
- BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 ※いろいろな解説があるので、ざっと見ておくとよいでしょう