@blog.justoneplanet.info

/**
 * 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に蓄えるので巨大グラフでは巨大なストレージが必要となる
• スタートから辿れない頂点は基本的には訪問しない