重み付き無向グラフの最小全域木を求めるアルゴリズム。任意の辺から始めて全頂点を覆うまで連続的に木の大きさを拡大し、全ての辺の重みの総和が最小となる経路を求める。
■実装
以下のように実装した。
/**
* 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);
結果
最小全域木の距離の総和は以下を足した値となる。
| 0 | 2 | 3 | 5 | 1 |
計算時に辿った経路は以下のようになる。
| -1 | 0 | 1 | 2 | 2 |
優先度付きキュー
以前の記事で使用したコードにメソッドを追記して使用した。
/**
* 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;
}
inQueueメッソドを効率よくできないかな・・・(●´⌓`●)