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

# はじめに

この記事は、Kahn’s algorithmを理解するための個人的メモです。はじめにKahn’s algorithmを文字ベースで説明した後、[geeksforgeeksのトポロジカルソートのページ](https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/)で掲載されているJavaScriptのKahn’s algorithmを参考に、コードでの実装を見ていきます。


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

ただし、トポロジカルソートの定義に関しては[wikiのトポロジカルソートのページ](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)などにまとまっているため割愛します。


# Kahn’s algorithm (文字ベース)

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

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

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


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

![graph.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309178/4d5c80fe-8bb1-193b-1279-30ff5a785648.png)



# Kahn’s algorithmのコード全文

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

``` Javascript
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);`の行の関数呼び出し以降は、トポロジカルソートのプログラムの実行例です。
以下のような有向グラフを定義し、トポロジカルソートを行って結果をコンソールに出力します。


![graph.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309178/4d5c80fe-8bb1-193b-1279-30ff5a785648.png)


## グローバル変数

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

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

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

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

例:
adj[3] = [0, 4];
```
上記の例は、以下のグラフを表します(idが1と2のノードは省略しています)。
![node.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309178/5b689ac6-1d67-e1da-f82d-c2a2bbf22bed.png)


## 関数

### Graph関数

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

### addEdge関数

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

### topologicalSort関数

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

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

```　Javascript
// 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文に入る前
![graph.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309178/4d5c80fe-8bb1-193b-1279-30ff5a785648.png)

例: while文に入る前
while文一周目の後
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309178/d8713b39-f115-dcea-aeb9-830090c247fc.png)

これを配列`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)](https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/) 

[トポロジカルソート(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)