幅優先探索 (BFS)
Coddyの「グラフ - データ構造シリーズ #9」コースのレッスン 10/14。
次のチャレンジは、作成したばかりの Graph クラスを使用するように設計されています。
各チャレンジには、ロックされた graph ファイル（前の章の最終的な Graph）と、Graph を使用する関数を記述するための新しい solution ファイルが含まれています。
最初のアルゴリズムは、幅優先探索（Breadth-First Search）です。BFSは、ある頂点から開始し、到達可能なすべての頂点を波のように訪問します。まず開始点、次に1エッジ離れたすべての頂点、次に2エッジ離れたすべての頂点、といった具合です。典型的な実装では キュー（queue） を使用します。開始点をエンキューし、繰り返しデキューして、その頂点を訪問済みとして記録し、未訪問の隣接する頂点をすべてエンキューします。
隣接リストには固定された順序がないため、2つの正しいBFS実行結果でも、トラバーサル（走査）順序が異なる場合があります。このチャレンジで答えを一意に定めるために、各頂点の隣接ノードをエンキューする前に 昇順 にソートしてください。
チャレンジ
簡単2次元整数配列 adjacency（各行は [u, v] のエッジ）と整数の start を受け取り、start からのBFS（幅優先探索）の訪問順序を整数のリストとして返す関数 bfs を作成してください。
グラフの構築：adjacency 内の各 [u, v] に対して、g.addEdge(u, v) を呼び出します。その後、キューを使用して start からBFSを実行します。頂点の隣接ノードを処理する際は、出力が決定論的になるように昇順にソートしてください。
必ず Graph クラスを使用してください（graph で提供されています）。隣接関係をモデル化するために言語組み込みの機能（マップ、セットなど）を使用しないでください。アルゴリズムの補助データ（訪問済みセット、キューなど）には標準ライブラリの型を使用しても構いません。
自分で試してみよう
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}