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