Implementation (Part 2)
Coddyの「トポロジカルソート - グラフアルゴリズム」コースのレッスン 6/9。
次に、入次数が0の頂点を繰り返し取り除き、順序を構築します。
チャレンジ
中級それでは、完全な順序付けを構築しましょう。
n とフラットな edges 配列（有向 u -> v）を受け取り、頂点のトポロジカル順序を返す topologicalSort という名前の関数を作成してください。
Kahnのアルゴリズムを使用します。入次数を計算し、入次数が0である頂点のうち**最小の**ものを繰り返し取り出し、それを追加して、その出力隣接頂点の入次数を減らします。このチャレンジの入力は非巡回（acyclic）です。
各ステップで利用可能な最小の頂点を選択することで、答えが一意になります。
自分で試してみよう
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// ここにコードを記述してください
*returnSize = 0;
return edges;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
トポロジカルソート - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity