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

学生向け

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

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

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

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

Mathematicaの新しいバージョンではパッケージ名が変わっています。

Needs["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}

これだけです（UMMでも動きます）。

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

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

新しいバージョンでは「GraphPlot[g, VertexLabeling -> True, DirectedEdges -> True]」としてください。

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

inquisitor