トポロジカル・ソート（それが目的ではないとき）

学生向け

トポロジカル・ソートを簡単に行う方法を教えてください

と訊かれました。Knuth の2.2.3を読んで実装すれば勉強になります。結果がほしいだけなら、すでに実装されているものを使いましょう。たとえば、Mathematicaなら次のようになります

必要なライブラリの読み込み

<< DiscreteMath`GraphPlot`
<< DiscreteMath`Combinatorica`

グラフを生成

g = FromOrderedPairs@{
  {9, 2}, {3, 7}, {7, 5}, {5, 8}, {8, 6},
  {4, 6}, {1, 3}, {7, 4}, {9, 5}, {2, 8}};

そして、トポロジカル・ソート

TopologicalSort@g

{1, 9, 3, 2, 7, 4, 5, 8, 6}

これだけです

せっかくなので、グラフを図示しておきましょう。そもそも、絵を描いておかないと何をやっているのかわからないでしょうし（ここでは、$TextStyle = {FontFamily -> "Helvetica", FontSize -> 18};でフォントを設定しています）

GraphPlot[g,
    "VertexStyleFunction" -> (Text[#, #] &),
    "EdgeStyleFunction" -> Automatic];

Knuthが、「興味深いプロジェクトとして、読者に残しておこう」と言う（主記憶に入らないような）大きなネットワークについては、また別の機会に書きましょう