辺の向きを先に定義する
トポロジカル順序は、有向辺u→vがあるときuをvより前へ置く頂点の並びです。依存関係を表すなら、前提となる作業から後続作業へ辺を張ります。「vがuへ依存する」という言葉だけで向きを逆にすると、出力の解釈も逆になります。この順序が存在するのは有向非巡回グラフ、DAGの場合です。最短路や重みの小さい順序を求めているわけではありません。辺のない頂点も作業として含め、頂点集合全体を扱う必要があります。
入次数0から取り出す
辺A→C、B→C、C→Dなら、最初に入次数0なのはAとBです。Aを取り出してCの入次数を2から1へ減らし、Bを取り出すと0になるのでCを待ち行列へ入れます。Cを取り出してDを0にし、[A,B,C,D]を得ます。AとBの取り出し順を逆にした[B,A,C,D]も正解です。取り出した頂点から出る辺だけを削除したと考え、残るグラフで前提のない頂点を次の候補にするのがKahn法の意味です。
閉路は残った頂点で分かる
全頂点数をVとして、取り出せた頂点がV個未満のまま待ち行列が空になれば、未処理部分に有向閉路があります。例えばC→DにD→Cを加えると、AとBを処理してもCとDは互いに入次数を持ち続けます。ただし残った頂点がすべて閉路上とは限らず、閉路の下流で待たされている頂点も含みます。閉路そのものの列を示したいなら別途探索が必要です。自己ループや多重辺も入次数の計算と減算で一貫して数えます。
計算量と一意性を分ける
隣接リストと通常の待ち行列を使えば、各頂点と各辺を一度ずつ扱うので時間O(V+E)、補助領域O(V)です。隣接リスト自体の保持にはO(V+E)を要します。候補の頂点を辞書順最小で選びたいなら優先度付きキューを使えますが、時間評価は変わります。複数の候補が同時にあることは、正しい順序が一意でない手掛かりです。順序の一意性、辺の整合性、実際の並列実行時に必要な資源制約は、それぞれ別の問題として考えます。