深さ優先探索 (DFS)
Coddyの「グラフ - データ構造シリーズ #9」コースのレッスン 11/14。
深さ優先探索は、横に広がる前に深く進みます。頂点から開始し、1つの辺を可能な限り遠くまで辿り、その後バックトラックして次の辺を試します。反復的なバージョンではスタックを使用します。頂点をポップして記録し、未訪問の隣接頂点をスタックにプッシュします。
このチャレンジでDFSに決定論的な探索順序を生成させるには、隣接頂点を逆順にソートしてプッシュしてください。そうすることで、最小の隣接頂点がスタックの最上部に配置され、最初に処理されるようになります。これは、昇順の隣接頂点に対して再帰的なDFSが行う順序と一致します。
頂点が2回プッシュされる可能性があることに注意してください（異なる隣接頂点が同じ頂点を持っている場合があります）。ループの先頭で訪問済みセットを確認し、すでに訪問されている場合はスキップします。
チャレンジ
簡単2次元整数配列 adjacency（各行は [u, v] のエッジ）と整数の start を受け取り、start からのDFS（深さ優先探索）の訪問順序を整数のリストとして返す関数 dfs を作成してください。
各エッジを追加してグラフを構築します。スタックを使用した反復的なDFSを行います。頂点をポップし、未訪問であればそれを記録し、その隣接ノードを降順にソートしてスタックにプッシュすることで、最も小さい値が最初に処理されるようにします。
必ず 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 = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}