Implementation (Part 2)
Coddyの「深さ優先探索 - グラフアルゴリズム」コースのレッスン 6/9。
それでは、スタックを使ってグラフ全体を探索します。
チャレンジ
中級それでは、完全な探索を構築しましょう。
n、フラットな edges 配列（無向）、および start 頂点を受け取り、start から始まる DFS が頂点を訪問する順序を返す、dfs という名前の関数を作成してください。
まず、隣接リストを作成します（各頂点の隣接ノードを昇順にソートします）。次に、スタックを使用して反復的な DFS を実行します。start から到達可能な頂点のみが訪問されます。
隣接ノードを昇順で訪問するには、それらを大きい順から小さい順にスタックにプッシュします。
自分で試してみよう
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// ここにコードを記述してください
*returnSize = 0;
return edges;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
深さ優先探索 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity