はじめに
この記事は、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がなくなるまで繰り返します。
- 配列
qからノードidを一つ取り出します。 - 1.で取り出したidを配列
topOrderの一番最後に追加します。 - 配列
adjから、1.で取り出したidのノードの後ろにつながるノードidを全て取り出します。 - 配列
indegreeの、3.で取り出したすべてのid番目の要素を1減らします。 - 4.の引き算で配列
indegreeの要素が0になったものがあれば、その要素に対応するidを配列'q'に保存します。
それぞれの変数の役割を入れて冗長に書くとこうなります。
- 入次数が0のノードidの配列
qからノードidを一つ取り出します。 - 1.で取り出したidを配列
topOrderの一番最後に追加します。 - 辺の情報が保存されている配列
adj(グローバル変数)から、1.で取り出したidのノードの後ろにつながるノードidを全て取り出します。 - 入次数の数が保存されている配列
indegreeの、3.で取り出したすべてのid番目の要素を1減らします。 - 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を文字ベースとコードベースの両方から見てみました。
読んでくださった方に何か発見や、理解の助けになる部分があれば幸いです。
読んでいただきありがとうございました。