JavaScriptで深さ優先探索
■実装
/**
* 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);
■特性
- グラフ全体を見通して経路を生成することはできず、求められる経路は最短経路ではない
- 無向グラフでも有向グラフでも機能する
- グラフ探索において情報蓄積量が最小
TrackBack URL :
Comments (1)