Implementation (Part 1)
Coddyの「トポロジカルソート - グラフアルゴリズム」コースのレッスン 5/9。
まずは、Kahnのアルゴリズムの核心である入次数から始めます。
チャレンジ
簡単Kahnのアルゴリズムの核心は、各頂点の入次数（in-degree）です。まずはそれを計算しましょう。
n とフラットな edges 配列（有向ペア u -> v）を受け取り、インデックス v の値が頂点 v に向かうエッジの数となる配列を返す、inDegrees という名前の関数を作成してください。
例えば、inDegrees(4, [0,1, 0,2, 1,3, 2,3]) は [0, 1, 1, 2] を返します。
自分で試してみよう
#include <stdlib.h>
int* inDegrees(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