@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);

// set up connections
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 discovered = [];
var finished   = [];
var counter    = 0;
for(var i = 0; i < vertexes.length; i++){
    pred[vertexes[i].value]       = -1;
    discovered[vertexes[i].value] = -1;
    finished[vertexes[i].value]   = -1;
}

/**
 * depthFirstSearch
 * @param array vertexes
 */
var depthFirstSearch = function(vertexes){
    depthFirstVisit(s);// start地点から探索
    // 以下の処理でstart地点から辿れない頂点を探索
    for(var i = 0; i < vertexes.length; i++){
        if(vertexes[i].state === 0){
            depthFirstVisit(vertexes[i]);
        }
    }
} 

/**
 * depthFirstVisit
 * @param Vertex vertex
 */
var depthFirstVisit = function(vertex){
    vertex.state = 1;// 探索した事を記録（再帰処理部分で自身を再訪しないように）
    discovered[vertex] = ++counter;
    // 以下の処理で隣接点を探索
    for(var i = 0; i < vertex.neighbor.length; i++){
        if(vertex.neighbor[i].state === 0){
            pred[vertex.neighbor[i].value] = vertex.value;
            depthFirstVisit(vertex.neighbor[i]);
        }
    }
    vertex.state = 2;// 全ての隣接点を探索した事を記録
    finished[vertex.value] = ++counter;
}
depthFirstSearch(vertexes);

// 1つ前の節点の値
console.log(pred);// [-1, 0, 1, 2, 3, 4, -1, 6, -1, 3]
// g<-3(v3)<-2(v2)<-1(v1)<-0(s)

// 発見したときのカウンタの値
console.log(discovered);// [1, 2, 3, 4, 5, 6, 15, 16, 19, 9]

// 探索し終えたときのカウンタの値
console.log(finished);// [14, 13, 12, 11, 8, 7, 18, 17, 20, 10]

console.log(vertexes);

■特性

• グラフ全体を見通して経路を生成することはできず、求められる経路は最短経路ではない
• 無向グラフでも有向グラフでも機能する
• グラフ探索において情報蓄積量が最小