はじめに

この記事は、Kahn’s algorithmを理解するための個人的メモです。はじめにKahn’s algorithmを文字ベースで説明した後、geeksforgeeksのトポロジカルソートのページで掲載されているJavaScriptのKahn’s algorithmを参考に、コードでの実装を見ていきます。

個人的メモではありますが、他の人のコードを見て実装はできるけど内部で何やってるかわからない、他のサイトのKahn’s algorithmがわかりにくい、という人の助けになる…かもしれません。

ただし、トポロジカルソートの定義に関してはwikiのトポロジカルソートのページなどにまとまっているため割愛します。

Kahn’s algorithm (文字ベース)

Kahn’s algorithmは以下の1～6の手順によりトポロジカルソートを行うアルゴリズムです。

n=1とする
グラフから入次数(定義は後で説明します)が0のノードを一つ選ぶ
2で選んだノードをトポロジカルソートの結果のn番目のノードとする
nにn+1を代入する
グラフから、2で選んだノードと、そのノードから他のノードに向かう辺を削除する
上の2～5を入次数が0のノードがなくなるまで繰り返す
入次数が0のノードがなくなれば成功・なくならなければ失敗

6で入次数が0のノードがなくなってもまだグラフにノードが残っている場合、残ったノードには循環部分があるためにトポロジカルソートは不可能(失敗)です。

※入次数とは、他のノードから対象のノードに向かう辺の数です。例えば、以下のグラフの5のノードの入次数は0、0のノードの入次数は2です。

Kahn’s algorithmのコード全文

以下がgeeksforgeeksに載っていたコードです。元のコメントは削除しました。topologicalSort関数内には、何をやっている部分かのコメントを追加しました。後ろでより詳しく見ていきます。

let V;
let adj;

function Graph(v)
{
    V = v;
    adj = new Array(V);
    for (let i = 0; i < V; i++)
        adj[i] = [];
}

function addEdge(u, v)
{
    adj[u].push(v);
}

function topologicalSort()
{
    // 1. グラフの入次数を計算する
    let indegree = new Array(V);
    for(let i = 0; i < V; i++)
        indegree[i] = 0;

    for (let i = 0; i < V; i++) {
        let temp
            = adj[i];
        for (let node = 0; node < temp.length; node++) {
            indegree[temp[node]]++;
        }
    }

    //　2. 入次数が0のノードを探す
    let q = [];
    for (let i = 0; i < V; i++) {
        if (indegree[i] == 0)
            q.push(i);
    }

    // 3. トポロジカルソートする
    let cnt = 0;
    let topOrder = [];
    while (q.length!=0)
    {
        let u = q.shift();
        topOrder.push(u);

        for (let node = 0; node < adj[u].length; node++)
        {
            if (--indegree[adj[u][node]] == 0)
                q.push(adj[u][node]);
        }
        cnt++;
    }

    // 4. ソートに失敗した場合のエラーを出す
    if (cnt != V) {
        document.write(
            "There exists a cycle in the graph");
        return;
    }

    // 5. 結果を出力する
    for (let i = 0; i < topOrder.length; i++)
    {
        document.write(topOrder[i] + " ");
    }
}

Graph(6);
addEdge(5, 2);
addEdge(5, 0);
addEdge(4, 0);
addEdge(4, 1);
addEdge(2, 3);
addEdge(3, 1);
document.write(
"Following is a Topological Sort<br>");
topologicalSort();

// This code is contributed by avanitrachhadiya2155

コードのメモ

コードでは2つのグローバル変数と、3つの関数が定義されます。これらを用いてトポロジカルソートが行われます。

コード下の方のGraph(6);の行の関数呼び出し以降は、トポロジカルソートのプログラムの実行例です。
以下のような有向グラフを定義し、トポロジカルソートを行って結果をコンソールに出力します。

グローバル変数

V

グラフのノード数を保存するための変数です。Vには整数(ノード数)が代入されます。

作成されたノードにはそれぞれ(0)～(要素数-1)のidが振られます。このノードのidを使って辺が定義されます。

adj

グラフの辺の情報を保存するための変数です。adjには2次元配列が代入されます。その2次元配列の要素は整数です。adjは、次のようにグラフの辺の情報を表します。

adj[(前のノードのid)] = (後ろのノードのidの配列);

例:
adj[3] = [0, 4];

上記の例は、以下のグラフを表します(idが1と2のノードは省略しています)。

関数

Graph関数

ノードを定義する関数です。引数は整数です。これはグラフのノード数を表していて、(0)から(Graph関数-1)までのidを持つノードが使えるようになります。

addEdge関数

辺を定義する関数です。引数は2つとも整数です。(第一引数のノードid) -> (第二引数のノードid)の向きの辺が定義されます。

topologicalSort関数

Kahn’s algorithmを実行する関数です。長いので細かく分けて見ていきます。

1. グラフの入次数を計算する

// 1. グラフの入次数を計算する
let indegree = new Array(V);
for(let i = 0; i < V; i++)
    indegree[i] = 0;

for (let i = 0; i < V; i++) {
    let temp
        = adj[i];
    for (let node = 0; node < temp.length; node++) {
        indegree[temp[node]]++;
    }
}

グラフ内のすべてのノードの入次数を計算して、結果を配列indegreeに保存します。1つ目のfor文で入次数の計算結果を入れる配列を初期化し、2つ目のfor文(2重のfor文)でグローバル変数adjから辺の情報を取ってきて入次数を計算します。

入次数の数は配列indegreeに以下のように保存されます。

indegree[(ノードのid)] = (ノードのidに対応する入次数);

上のグラフでの例: 
indegree[0] = 2;
indegree[5] = 0;

2. 入次数が0のノードを探す

//　2. 入次数が0のノードを探す
let q = [];
for (let i = 0; i < V; i++) {
   if (indegree[i] == 0)
        q.push(i);
}

入次数が0のノードのidを配列qに保存します。

3. トポロジカルソートする

let cnt = 0;
let topOrder = [];
while (q.length!=0)
{
    let u = q.shift();
    topOrder.push(u);

    for (let node = 0; node < adj[u].length; node++)
    {
        if (--indegree[adj[u][node]] == 0)
            q.push(adj[u][node]);
    }
    cnt++;
}

配列indegreeと配列qを用いてトポロジカルソートした結果を配列topOrderに保存します。変数cntはトポロジカルソートしたノードの数で、topOrder.lengthと等しくなります。

while文では、以下の処理を配列qがなくなるまで繰り返します。
1. 配列qからノードidを一つ取り出します。
2. 1.で取り出したidを配列topOrderの一番最後に追加します。
3. 配列adjから、1.で取り出したidのノードの後ろにつながるノードidを全て取り出します。
4. 配列indegreeの、3.で取り出したすべてのid番目の要素を1減らします。
5. 4.の引き算で配列indegreeの要素が0になったものがあれば、その要素に対応するidを配列'q'に保存します。

それぞれの変数の役割を入れて冗長に書くとこうなります。
1. 入次数が0のノードidの配列qからノードidを一つ取り出します。
2. 1.で取り出したidを配列topOrderの一番最後に追加します。
3. 辺の情報が保存されている配列adj(グローバル変数)から、1.で取り出したidのノードの後ろにつながるノードidを全て取り出します。
4. 入次数の数が保存されている配列indegreeの、3.で取り出したすべてのid番目の要素を1減らします。
5. 4.の引き算で配列indegreeの要素が0になったものがあれば、その要素に対応するidを配列qに保存します。

3.と4.でやっていることのイメージとしては、考える対象のグラフの縮小です。Kahn’s algorithm (文字ベース)では、「5. グラフから、2で選んだノードと、そのノードから他のノードに向かう辺を削除する」に対応します。入次数が0のノードと、そのノードから出ていく辺を削除し、グラフを縮小する感じです。

例: while文に入る前

例: while文に入る前
while文一周目の後

これを配列qが0になるまで繰り返すことで、巡回グラフである場合を除いて、全てのノードのトポロジカルソートが完了します。グラフに巡回している部分がある場合、巡回している部分のノードの入次数が0にならないためにソートされない、すなわち配列topOrderに入らないノードidが存在します。

4. ソートに失敗した場合のエラーを出す

// 4. ソートに失敗した場合のエラーを出す
if (cnt != V) {
    document.write(
        "There exists a cycle in the graph");
    return;
}

巡回グラフである場合にエラーを返します。

変数cntは配列topOrderの要素数と等しく、Vはグラフ中の全ノード数です。これらが異なることは、「3. トポロジカルソートする」の最後に書いた通り、巡回部分があって一部ソートできていないことを意味します。

5. 結果を出力する

// 5. 結果を出力する
for (let i = 0; i < topOrder.length; i++)
{
    document.write(topOrder[i] + " ");
}

トポロジカルソートした結果を返します。

おわりに

Kahn’s algorithmを文字ベースとコードベースの両方から見てみました。
読んでくださった方に何か発見や、理解の助けになる部分があれば幸いです。

読んでいただきありがとうございました。

参考文献

Kahn’s algorithm for Topological Sorting (geeksforgeeks)

トポロジカルソート(Wikipedia)

JavaScriptでトポロジカルソートを行うKahn’s algorithmのメモ