@blog.justoneplanet.info

レーベンシュタイン距離を使う。

function mb_str_split($str, $split_len = 1) {
    mb_internal_encoding('UTF-8');
    mb_regex_encoding('UTF-8');
    if ($split_len <= 0) {
        $split_len = 1;
    }

    $strlen = mb_strlen($str, 'UTF-8');
    $ret    = array();

    for ($i = 0; $i < $strlen; $i += $split_len) {
        $ret[] = mb_substr($str, $i, $split_len);
    }
    return $ret;
}

function getLevenshteinFactor($string1, $string2, $insert = 1, $delete = 1, $replace = 1) {
    $string1 = mb_str_split($string1);
    $length1 = count($string1);
    $string2 = mb_str_split($string2);
    $length2 = count($string2);

    if ($length1 < $length2) {
        $c = $string1;
        $string1 = $string2;
        $string2 = $c;
        $o = $length1;
        $length1 = $length2;
        $length2 = $o;
    }

    $d = array();
    $d[0] = array();
    for ($i = 0; $i < $length2 + 1; $i++) {
        $d[0][$i] = $i;
    }

    for ($i = 1; $i < $length1 + 1; $i ++) {
        $d[$i] = array();
        $d[$i][0] = $i;
        for ($j = 1; $j < $length2 + 1; $j ++) {
            $cost = ($string1[$i - 1] === $string2[$j - 1]) ? 0 : 1;
            $d[$i][$j] = min(
                $d[$i - 1][$j] + $insert,
                $d[$i][$j - 1] + $delete,
                $d[$i - 1][$j - 1] + ($replace * $cost)
            );print($d[$i][$j]);
        }
    }
    $distance = $d[$length1][$length2];
    $rate = $distance / $length1;
    return $rate;
}

他のサイトから持ってきたけど期待した値と少し違ったので調整した。

Extensionとか入れたりするの面倒なので以下のJavaScriptをコンソールに打ち込む。

var ary = [];
for(var i = 0; i < 1024; i++){
    if($('card' + i)){
        $('#card' + i).click();
        ary.push($('#card' + i).css('backgroundColor'));
    }
}
ary.forEach(function(elm, i1, ary){
    for(var i2 = i1 + 1; i2 < ary.length; i2++){
        if(ary[i1] == ary[i2]){
            $('#card' + i1).click();
            $('#card' + i2).click();
        }
    }
});

重み付き無向グラフの最小全域木を求めるアルゴリズム。任意の辺から始めて全頂点を覆うまで連続的に木の大きさを拡大し、全ての辺の重みの総和が最小となる経路を求める。

■実装

以下のように実装した。

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var v0 = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
v0.appendNeighbor(
    {"vertex" : v1, "weight" : 2},
    {"vertex" : v3, "weight" : 8},
    {"vertex" : v4, "weight" : 4}
);
v1.appendNeighbor(
    {"vertex" : v0, "weight" : 2},
    {"vertex" : v2, "weight" : 3}
);
v2.appendNeighbor(
    {"vertex" : v1, "weight" : 3},
    {"vertex" : v4, "weight" : 1},
    {"vertex" : v3, "weight" : 5}
);
v3.appendNeighbor(
    {"vertex" : v2, "weight" : 5},
    {"vertex" : v4, "weight" : 7},
    {"vertex" : v0, "weight" : 8}
);
v4.appendNeighbor(
    {"vertex" : v2, "weight" : 1},
    {"vertex" : v3, "weight" : 7},
    {"vertex" : v0, "weight" : 4}
);
var V = [v0, v1, v2, v3, v4];

// initialize
var key  = [];
var pred = [];
for(var i = 0; i < V.length; i++){
    key[V[i]['value']]  = Number.POSITIVE_INFINITY;
    pred[V[i]['value']] = -1;
}
key[0] = 0;// 任意の1頂点をスタート地点とするため優先度を0にする
var bh = new BinaryHeap();
for(var i = 0; i < V.length; i++){
    // 頂点を優先度付きキューに格納
    bh.insert(V[i], key[V[i]['value']]);
}

// calc
while(bh.getList().length > 0){
    var u = bh.getPrior();// 優先度で先頭にくる頂点を取り出す
    for(var i = 0; i < u['neighbor'].length; i++){// 経路が存在している頂点でループ
        var neighbor = u['neighbor'][i]['vertex'];
        // 頂点(a)がキューに存在している場合
        if(bh.inQueue(neighbor)){
            var weight = u['neighbor'][i]['weight'];
            // かつ頂点(a)まで距離が前回のループまでに到達した距離よりも短い場合
            if(weight < key[neighbor['value']]){
                pred[neighbor['value']] = u['value'];// 頂点を配列に格納
                key[neighbor['value']]  = weight;// 距離を配列に格納
                bh.changePriority(neighbor, weight);// 優先度を更新（キューの先頭に近づく）
            }
        }
    }
}

// result
console.log("key:");
console.log(key);
console.log("pred:");
console.log(pred);

結果

最小全域木の距離の総和は以下を足した値となる。

計算時に辿った経路は以下のようになる。

/**
 * BinaryHeap
 */
var BinaryHeap = function(){
    var self = this;
    self._ary  = [];
}
BinaryHeap.prototype._build = function(){
    var self = this;
    /**
     * heapify
     * 3要素を比較し最も小さい要素を親とする
     * @param {array} ary
     * @param {int} i
     * @param {max} max
     */
    var heapify = function(ary, i, max){
        /**
         * swap
         * @param {array} ary
         * @param {int} x
         * @param {int} y
         */
        var swap = function(ary, x, y){
            var a = ary[x];
            var b = ary[y];
            ary[x] = b;
            ary[y] = a;
            return true;
        }

        var l = 2 * i + 1;
        var r = 2 * i + 2;
        var li = 0;
        if(l < max && ary[l].priority < ary[i].priority){
            li = l;
        }
        else{
            li = i;
        }
        if(r < max && ary[r].priority < ary[li].priority){
            li = r;
        }
        if(li !== i){
            swap(ary, i, li);
            heapify(ary, li, max);
        }
    }
    var ary = self._ary;
    for(var i = ary.length - 1; i >= 0; i--){
        heapify(ary, i, self._ary.length);
    }
}
/**
 * BinaryHeap::insert
 * 要素をヒープに追加する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.insert = function(elm, priority){
    var self = this;
    self._ary.push({
        "priority" : priority,
        "elm"      : elm
    });
    self._build();
}
/**
 * BinaryHeap::changePriority
 * 要素の優先度を変更する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.changePriority = function(elm, priority){
    var self = this;
    var ary  = self._ary;
    for(var i = 0; i < ary.length; i++){
        if(elm === ary[i]["elm"]){
            ary[i]["priority"] = priority;
            self._build();
            return true;
        }
    }
    return false;
}
/**
 * BinaryHeap::getPrior
 * 優先度の高い要素を取得する
 */
BinaryHeap.prototype.getPrior = function(){
    var self = this;
    var elm  = self._ary.shift();
    self._build();
    return elm["elm"];
}
/**
 * BinaryHeap::getList
 * ヒープを返す
 */
BinaryHeap.prototype.getList = function(){
    var self = this;
    return self._ary;
}

/**
 * BinaryHeap::inQueue
 * ヒープ内で探索
 */
BinaryHeap.prototype.inQueue = function(v){
    var self = this;
    for(var i = 0; i < self._ary.length; i++){
        if(self._ary[i]['elm'] === v){
            return true;
        }
    }
    return false;
}

■実装

以下のように実装した。

//Graph
var vertexes = [
     [null, 2,    null, null, 4],//    vertex 1
     [null, null, 3,    null, null],// vertex 2
     [null, null, null, 5,    1],//    vertex 3
     [8,    null, null, null, null],// vertex 4
     [null, null, null, 4,    null]//  vertex 5
];

// initialize
var dist = [];
var pred = [];
var n    = vertexes.length;
for(var u = 0; u < n; u++){
    dist[u] = [];
    pred[u] = [];
    for(var i = 0; i < n; i++){
        dist[u][i] = Number.POSITIVE_INFINITY;// 経路が存在しない場合は無限
        pred[u][i] = -1;
        if(vertexes[u][i] !== null){
            dist[u][i] = vertexes[u][i];// 元グラフの経路を代入
            pred[u][i] = u;
        }
    }
    dist[u][u] = 0;// 自身に対しては0の距離が存在する
}
console.log('dist:');
console.log(dist);//...(a)

// 計算
for(var k = 0; k < n; k++){
    for(var i = 0; i < n; i++){
        if(dist[i][k] === Number.POSITIVE_INFINITY){
            continue;
        }
        // 任意の頂点まで有限の距離が開いているとき
        // 有限距離 を経由した任意の頂点を選択し
        // そこまでの距離が既に計算したものよりも小さい場合に
        // その値で上書きする
        for(var j = 0; j < n; j++){
            var newLength = dist[i][k];// ik
            newLength += dist[k][j];
            if(newLength < dist[i][j]){
                dist[i][j] = newLength;
                pred[i][j] = pred[k][j];
            }
        }
    }
}

// 結果
console.log("dist:");
console.log(dist);//...(b)

(a)の時、distは以下のようになる。

殆ど元グラフと変わらない。結果(b)は、以下のようになる。

例えば0→1は距離が2、0→2は距離が5、0→3は距離が8、0→4は距離が4であり、1→0は距離が16である。

経路

終了時のpredは以下のようになる。

例えば0→1の一つ前の頂点は始点0、0→2の一つ前の頂点は頂点1、0→3の一つ前の頂点は頂点4、0→4の一つ前の頂点は0であり、1→0の場合は頂点3が終点の一つ前である。

■おまけ

ちなみに表は以下のようにして描画した。

document.write('<table border="1" cellpadding="0" cellspacing="0">');
dist.forEach(function(e1, i1, ary1){
	document.write('<tr>');
	e1.forEach(function(e2, i2, ary2){
		document.write('<td>' + e2 + '</td>');
	});
	document.write('</tr>');
});
document.write('</table>');

そろそろJavaScriptでもforEachを使って良い頃だと思う。

■実装

グラフは以下のようにして実装した。グラフは前回のものと同様だがベルマンフォード法では負の重みも存在しうるので、経路が存在しない部分はnullとした。

// Graph //前回のグラフと同じグラフを使用
var vertexes = [
     [null, 1,    3,    null, null, null],// vertex s
     [null, null, 1,    4,    null, null],// vertex 1
     [null, null, null, 1,    null, null],// vertex 2
     [null, null, null, null, 1,    10],//   vertex 3
     [null, null, null, null, null, 1],//    vertex 4
     [null, null, null, null, null, null] // vertex g
];

// initialize
var dist    = [];
var pred    = [];
for(var i = 0; i < vertexes.length; i++){
    dist[i] = Number.POSITIVE_INFINITY;
    pred[i] = -1;
}
dist[0] = 0;// start

// 計算
(function(){
    var n = vertexes.length;
    for(var i = 1; i <= n; i++){
        // i=nの時
        // destinationと自身が同じであるにも関わらず
        // 後述のnewLenの方が短い場合、
        // 負の閉路が存在していることを示す
        failOnUpdate = (i === n);
        leaveEarly   = true;
        for(var u = 0; u < n; u++){
            for(var ci = 0; ci < n; ci++){
                if(vertexes[u][ci] === null){continue;}//経路が存在しない
                var newLen = dist[u] + vertexes[u][ci];//頂点uを経由したciへの距離
                if(newLen < dist[ci]){// 頂点u経由の方が短い場合はアップデートする
                    if(failOnUpdate){
                        throw new Error('Graph has negative cycle');
                    }
                    dist[ci] = newLen;
                    pred[ci] = u;
                    leaveEarly = false;
                }
            }
        }
        if(leaveEarly){
            break;
        }
    }
})();

// 結果表示
console.log("最短経路");
console.log(pred);// [-1, 0, 1, 2, 3, 4]
console.log("最短距離");
console.log(dist);// [0, 1, 2, 3, 4, 5]

但し、上述の場合では負の重みが存在しない。

負の重み

従って以下のデータでテストしてみる。

var vertexes = [
     [null, 1,    3,    null, null, null],// s
     [null, null, 1,    4,    null, null],// 1
     [null, null, null, 1,    null, null],// 2
     [null, null, null, null, 1,    -10],// 3
     [null, null, null, null, null, 1],// 4
     [null, null, null, null, null, null] // g
];

以下のような結果となる。

console.log("最短経路");
console.log(pred);// [-1, 0, 1, 2, 3, 3]
console.log("最短距離");
console.log(dist);// [0, 1, 2, 3, 4, -7]

3→gの距離が4を経由するよりも近くなり、s〜gの重みは-7となった。

負の閉路

以下のように閉路（ループ）で総和が負の値になるような経路を用意する。

var vertexes = [
     [null, -1,   3,    null, null, null],// s
     [null, null, -10,  4,    null, null],// 1
     [5,    null, null, 1,    null, null],// 2
     [null, null, null, null, 1,    -10],// 3
     [null, null, null, null, null, 1],// 4
     [null, null, null, null, null, null] // g
];

以下のようなエラーが発生する。

//Uncaught Error: Graph has negative cycle

ベルマンフォード法は負の重みがあった場合でも処理が可能であるが、総和が0より小さい負の閉路が存在していた場合は使用できない。但し、そのような場合は最短経路自体が意味を成さない。ちなみに密グラフには向かないアルゴリズムであるので、多次元配列（行列）でのグラフ生成は良くないかもしれない。(●´⌓`●)

頂点を表すベクトルに対して乗算する事で以下のような操作ができる行列である。

■移動行列

 1,  0,  0, 1
 0,  1,  0, 0
 0,  0,  1, 0
dx, dy, dz, 1

■拡大縮小行列

zx,  0,  0, 0
 0, zy,  0, 0
 0,  0, zz, 0
 0,  0,  0, 1

■回転行列

XX(1 - cosθ) +  cosθ,  XY(1- cosθ) - Zsinθ,  XZ(1 - cosθ) + Ysinθ, 0
XY(1 - cosθ) + Zsinθ,  YY(1- cosθ) -  cosθ,  YZ(1 - cosθ) + Xsinθ, 0
XZ(1 - cosθ) + Ysinθ,  ZY(1- cosθ) + Xsinθ,  ZZ(1 - cosθ) +  cosθ, 0
                   0,                    0,                     0, 1

前回の記事では、生成するグラフが疎であったので連結リストを使用した。密グラフ向けに行列でも実装した。

■実装

// Graph //（密ではないが）前回のグラフと同じグラフを使用
var Vertexes = [
             [0, 1, 3, 0, 0, 0],// s
             [0, 0, 1, 4, 0, 0],// 1
             [0, 0, 0, 1, 0, 0],// 2
             [0, 0, 0, 0, 1,10],// 3
             [0, 0, 0, 0, 0, 1],// 4
             [0, 0, 0, 0, 0, 0] // g
];

// initialize
var dist    = [];
var pred    = [];
var visited = [];
for(var i = 0; i < Vertexes.length; i++){
    dist[i] = Number.POSITIVE_INFINITY;
    pred[i] = -1;
    visited[i] = false;// 訪問を記録する
}
dist[0] = 0;// start

// search
var dijkstraMX = function(){
    var getMin = function(){
        var tmp = Number.POSITIVE_INFINITY;
        for(var i = 0; i < Vertexes.length; i++){
            if(visited[i] === false && dist[i] < tmp){
                tmp = i;
            }
        }
        if(tmp === Number.POSITIVE_INFINITY){
            tmp = null;
        }
        return tmp;
    }

    while(true){
        var u = getMin();// 未訪問の中でスタートから最小の距離の頂点
        // 「sから辿れない頂点しか残っていない場合」「未訪問が無い場合」はループ終了
        if(dist[u] === Number.POSITIVE_INFINITY || u === null){break;}
        visited[u] = true;
        for(var i = 0; i < Vertexes[u].length; i++){
            if(Vertexes[u][i] > 0){// 辺が存在している
                var neighbor  = i;//隣接点(a)
                var weight    = Vertexes[u][i];// (a)との辺の重み
                var newLength = dist[u] + weight;// (b)
                // 現在セットされている、スタート地点から隣接点までの距離が
                // 新しい経路での値より大きい時
                if(newLength < dist[neighbor]){
                    dist[neighbor] = newLength;
                    pred[neighbor] = u;
                }
            }
        }
    }
}
dijkstraMX();

// 最短経路
console.log(pred);// [-1, 0, 1, 2, 3, 4]

// 最短距離
console.log(dist);// [0, 1, 2, 3, 4, 5]

グラフが疎である場合、行列を使用すると殆どの空間が0で埋められるので勿体無いね。

優先度つきキューを使用したダイクストラ法をJavaScriptで実装した。

■実装

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.state    = 0;
    self.dist     = Number.POSITIVE_INFINITY;// もしくは十分に大きい値とか
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var g  = new Vertex(5);

// set up connections
// 単純化のためループや往路を除去した
s.appendNeighbor(
    {"weight" : 1, "vertex" : v1},
    {"weight" : 3, "vertex" : v2}
);
v1.appendNeighbor(
    {"weight" : 1, "vertex" : v2},
    {"weight" : 4, "vertex" : v3}
);
v2.appendNeighbor(
    {"weight" : 1, "vertex" : v3}
);
v3.appendNeighbor(
    {"weight" : 1, "vertex" : v4},
    {"weight" : 10, "vertex" : g}
);
v4.appendNeighbor(
    {"weight" : 1, "vertex" : g}
);
g.appendNeighbor(
);

// initialize
var vertexes = [s, v1, v2, v3, v4, g];
var pred     = [];
var pq       = new BinaryHeap();// sからの距離が短い頂点順の優先度つきキュー
s.dist = 0;
for(var i = 0; i < vertexes.length; i++){// キューの生成
    pred[i] = -1;
    pq.insert(vertexes[i], vertexes[i].dist);
}

// search
var dijkstraPQ = function(){
    while(pq.getList().length > 0){
        var u = pq.getPrior();// スタートからの距離が近い頂点を取得しcurrent頂点とする
        for(var i = 0; i < u.neighbor.length; i++){
            var neighbor  = u.neighbor[i].vertex;
            var weight    = u.neighbor[i].weight;// 隣接点の距離...(a)
            var newLength = u.dist + weight;// current頂点のsからの距離と(a)を加算...(b)
            // (b) < visitした時の距離の場合
            // キューを更新し、最短経路も更新する
            if(newLength < neighbor.dist){
                pq.changePriority(neighbor, newLength);
                neighbor.dist = newLength;
                pred[neighbor.value] = u.value;
            }
        }
    }
}
dijkstraPQ();

// 最短経路
console.log(pred);// [-1, 0, 1, 2, 3, 4]
// g<-v4<-v3-<v2<-v1<-s

// 最短距離
console.log(g.dist);// 5

任意の頂点に対して一つ前の頂点とその時の距離が分かる。

■特性

• 辺の重みは0より大きい値
• 重みの和が0より小さい閉路が存在すると無限ループする可能性がある

/**
 * BinaryHeap
 */
var BinaryHeap = function(){
    var self = this;
    self._ary  = [];
}
BinaryHeap.prototype._build = function(){
    var self = this;
    /**
     * heapify
     * 3要素を比較し最も小さい要素を親とする
     * @param {array} ary
     * @param {int} i
     * @param {max} max
     */
    var heapify = function(ary, i, max){
        /**
         * swap
         * @param {array} ary
         * @param {int} x
         * @param {int} y
         */
        var swap = function(ary, x, y){
            var a = ary[x];
            var b = ary[y];
            ary[x] = b;
            ary[y] = a;
            return true;
        }
        
        var l = 2 * i + 1;
        var r = 2 * i + 2;
        var li = 0;
        if(l < max && ary[l].priority < ary[i].priority){
            li = l;
        }
        else{
            li = i;
        }
        if(r < max && ary[r].priority < ary[li].priority){
            li = r;
        }
        if(li !== i){
            swap(ary, i, li);
            heapify(ary, li, max);
        }
    }
    var ary = self._ary;
    for(var i = ary.length - 1; i >= 0; i--){
        heapify(ary, i, self._ary.length);
    }
}
/**
 * BinaryHeap::insert
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.insert = function(elm, priority){
    var self = this;
    self._ary.push({
        "priority" : priority,
        "elm"      : elm
    });
    self._build();
}
/**
 * BinaryHeap::changePriority
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.changePriority = function(elm, priority){
    var self = this;
    var ary  = self._ary;
    for(var i = 0; i < ary.length; i++){
        if(elm === ary[i]["elm"]){
            ary[i]["priority"] = priority;
            self._build();
            return true;
        }
    }
    return false;
}
/**
 * BinaryHeap::getPrior
 */
BinaryHeap.prototype.getPrior = function(){
    var self = this;
    var elm  = self._ary.shift();
    self._build();
    return elm["elm"];
}
/**
 * BinaryHeap::getList
 */
BinaryHeap.prototype.getList = function(){
    var self = this;
    return self._ary;
}

Cの場合は以下のようにして、二分ヒープを使用することができるらしい。

#include "BinaryHeap.h"

■実装

しかし、JavaScriptには二分ヒープのようなデータ構造が存在しないので、以下のように自力で実装する。

/**
 * BinaryHeap
 */
var BinaryHeap = function(){
    var self = this;
    self._ary  = [];
}
BinaryHeap.prototype._build = function(){
    var self = this;
    /**
     * heapify
     * 3要素を比較し最も小さい要素を親とする
     * @param {array} ary
     * @param {int} i
     * @param {max} max
     */
    var heapify = function(ary, i, max){
        /**
         * swap
         * @param {array} ary
         * @param {int} x
         * @param {int} y
         */
        var swap = function(ary, x, y){
            var a = ary[x];
            var b = ary[y];
            ary[x] = b;
            ary[y] = a;
            return true;
        }
        
        var l = 2 * i + 1;
        var r = 2 * i + 2;
        var li = 0;
        if(l < max && ary[l].priority < ary[i].priority){
            li = l;
        }
        else{
            li = i;
        }
        if(r < max && ary[r].priority < ary[li].priority){
            li = r;
        }
        if(li !== i){
            swap(ary, i, li);
            heapify(ary, li, max);
        }
    }
    var ary = self._ary;
    for(var i = ary.length - 1; i >= 0; i--){
        heapify(ary, i, self._ary.length);
    }
}
/**
 * BinaryHeap::insert
 * 要素をヒープに追加する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.insert = function(elm, priority){
    var self = this;
    self._ary.push({
        "priority" : priority,
        "elm"      : elm
    });
    self._build();
}
/**
 * BinaryHeap::changePriority
 * 要素の優先度を変更する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.changePriority = function(elm, priority){
    var self = this;
    var ary  = self._ary;
    for(var i = 0; i < ary.length; i++){
        if(elm === ary[i]["elm"]){
            ary[i]["priority"] = priority;
            self._build();
            return true;
        }
    }
    return false;
}
/**
 * BinaryHeap::getPrior
 * 優先度の高い要素を取得する
 */
BinaryHeap.prototype.getPrior = function(){
    var self = this;
    var elm  = self._ary.shift();
    self._build();
    return elm["elm"];
}
/**
 * BinaryHeap::getList
 * ヒープを返す
 */
BinaryHeap.prototype.getList = function(){
    var self = this;
    return self._ary;
}

// test code
var pq = new BinaryHeap();
pq.insert('pochi', 0);
pq.insert('son', 4);
pq.insert('mike', 10);
pq.insert('father', 1);
pq.insert('mother', 2);
console.log(pq.getList());

優先度つきキューに使用したいので、ヒープソートのコードを変更し最小ヒープとした。使用方法は以下のとおりである。

二分ヒープの生成

var pq = new BinaryHeap();

要素の追加

pq.insert(elm, priority);

優先度の変更

pq.changePriority(elm, priority);

最優先要素の取得

var elm = pq.getPrior();

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.state    = 0;
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var v5 = new Vertex(5);
var v6 = new Vertex(6);
var v7 = new Vertex(7);
var v8 = new Vertex(8);
var g  = new Vertex(9);
s.appendNeighbor(v1, v4);
v1.appendNeighbor(s, v2);
v2.appendNeighbor(v1, v3);
v3.appendNeighbor(v2, v4, g);
v4.appendNeighbor(v3, v5, s);
v5.appendNeighbor(v4);
v6.appendNeighbor(v7);
v7.appendNeighbor(v6);
g.appendNeighbor(v3);
var vertexes = [s, v1, v2, v3, v4, v5, v6, v7, v8, g];

// initialize
var pred       = [];
var distance   = [];
var queue = [];
var counter    = 0;
for(var i = 0; i < vertexes.length; i++){
    pred[vertexes[i].value]       = -1;
    distance[vertexes[i].value]   = -1;
}

// search
s.state = 1;
distance[s.value] = 0;
queue.push(s);
var breadthFirstSearch = function(){
    while(queue.length > 0){
        var vertex = queue.shift();// 処理する頂点
        for(var i = 0; i < vertex.neighbor.length; i++){// 隣接点全てに対して
            var n = vertex.neighbor[i];
            if(vertex.neighbor[i].state === 0){
                distance[n.value] = distance[vertex.value] + 1;// 処理中の頂点+1の距離
                pred[n.value]     = vertex.value;// 処理中の頂点の値
                n.state           = 1;// visitした記録
                queue.push(n);// 隣接点をキューに入れる
            }
        }
        vertex.state = 2;// 処理し終わった記録
    }
}
breadthFirstSearch();

// 1つ前の節点の値
console.log(pred);// [-1, 0, 1, 4, 0, 4, -1, -1, -1, 3]

// 各節点のスタートからの距離
console.log(distance);// [0, 1, 2, 2, 1, 2, -1, -1, -1, 3]

console.log(vertexes);

スタート地点から全体に探索菌が同速度で広がっていくイメージだね。

■特性

• 無向グラフでも有向グラフでも機能する
• 重みでなくステップ数での最短距離を求めることができる
• 節点をQueueに蓄えるので巨大グラフでは巨大なストレージが必要となる
• スタートから辿れない頂点は基本的には訪問しない