这段时间学算法，用JS实现了一个Prim，用于在连通图中找出最小树，具体内容、代码解析周末会不上，现在先把源码献上：
<!DOCTYPE html>
<html charset='GB2312'> <head>
<title>最小树生成算法</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <style type="text/css">
body>canvas {
border: 1px solid black;
padding: 10px;
margin: 10px auto;
}
</style>
</head> <body>
<canvas id="canvas" width="1000px" height="400px"></canvas>
<canvas id="sub-canvas" width="1000px" height="400px"></canvas>
<script type="text/javascript">
!(function() {
var canvas_context = document.getElementById('canvas').getContext('2d'),
sub_ctx = document.getElementById('sub-canvas').getContext('2d'),
_getRandom = function(max, min) {
max = max || 100;
min = min || 0;
return Math.round(Math.random() * (max - min) + min);
},
_getRandomMatix = function(nodes) {
var matix = [],
power = 0,
max = 10,
min = 0,
tmp = 0;
for (var i = 0; i < nodes; i++) {
for (var j = i; j < nodes; j++) {
power = _getRandom(max, min);
matix[i] = matix[i] || [];
matix[j] = matix[j] || [];
tmp = i === j ? 0 : (Math.random() > 0.6 ? 1 : 0) * power;
matix[i][j] = matix[j][i] = tmp;
}
console.log(matix[i].join(','))
} // 构造连通图
for (var i = 0; i < matix.length; i++) {
var isValid = true;
for (var j = 0; j < matix[i].length; j++) {
isValid = isValid && matix[i][j] !== 0;
}
if (!isValid) {
var rindex = _getRandom(matix[i].length - 1, 0),
v = _getRandom(max, min + 1);
matix[i][rindex] = matix[rindex][i] = v;
}
}
return matix;
},
_matix2graph = function(matix) {
var len = matix.length,
row = null,
cell = null,
graph = {},
x,
y;
canvas_context.font = cycle_width / 2 + 'px Arial bold';
canvas_context.textAlign = 'center';
for (var i = 0; i < len; i++) {
x = _getRandom(pain_rect.x2, pain_rect.x1);
y = _getRandom(pain_rect.y2, pain_rect.y1); graph[i] = {
x: x,
y: y,
powers: matix[i]
}
}
return graph;
},
_getMinTree = function(graph) {
var point1 = graph[0],
min_tree = {
x: point1.x,
y: point1.y,
index: 0,
sub: []
},
min_x = -1,
min_y = -1,
min = Number.MAX_VALUE,
index_inTree = [0],
node = null,
_findNode = function(index, roots) {
if (roots.length === 0) return null; var subRoots = [];
for (var i in roots) {
if (roots[i].index === index) return roots[i];
else subRoots = subRoots.concat(roots[i].sub);
}
return _findNode(index, subRoots);
}; for (var k in graph) {
min_x = -1;
min_y = -1;
min = Number.MAX_VALUE;
for (var i = 0; i < index_inTree.length; i++) {
point1 = graph[index_inTree[i]];
for (var j = 1; j < point1.powers.length; j++) {
if (index_inTree.indexOf(j) >= 0) continue;
else if (point1.powers[j] > 0 && point1.powers[j] < min) {
min_x = point1.index;
min_y = j;
min = point1.powers[j]
}
}
}
if (min_x >= 0) {
index_inTree.push(min_y);
point1 = graph[min_y];
node = _findNode(graph[min_x].index, [min_tree]);
if ( !! node) node.sub.push({
x: point1.x,
y: point1.y,
index: min_y,
power: min,
sub: []
});
}
console.log('min tree node count: ' + index_inTree.length + ' ; ' + node);
}
return min_tree;
},
canva_width = 1000,
canva_height = 400,
x_range = 490,
y_range = 190,
pain_rect = {
x1: canva_width / 2 - x_range,
x2: canva_width / 2 + x_range,
y1: canva_height / 2 - y_range,
y2: canva_height / 2 + y_range
},
cycle_width = 10,
_renderGraph = function(graph) {
var point1,
point2,
count = 0;
for (var i in graph) {
point1 = graph[i];
i = i - 0;
point1.index = i;
for (var j = 0; j < point1.powers.length; j++) {
point2 = graph[j];
point2.index = j; _renderPoint(point1);
_renderPoint(point2);
if ( !! point1.powers[j]) {
_renderLine(point1, point2, point1.powers[j]);
console.log('graph ' + i + ' to ' + j + ': ' + point1.powers[j]);
count += point1.powers[j];
}
}
}
console.log('end graph :' + count);
return graph;
},
_renderTree = function(tree) {
var _count = 0,
_renderer = function(root) {
var point1 = root,
point2 = null;
_renderPoint(point1, sub_ctx);
for (var i = 0; i < root.sub.length; i++) {
point2 = root.sub[i];
_renderLine(point1, point2, point2.power, sub_ctx);
_renderer(point2);
_count += point2.power;
console.log('tree ' + point1.index + ' to ' + point2.index + ' : ' + point2.power);
}
};
_renderer(tree); console.log('end tree :' + _count)
},
_renderPoint = function(point1, ctx) {
ctx = ctx || canvas_context;
requestAnimationFrame(function() {
// 画点
ctx.beginPath();
ctx.fillStyle = 'red';
ctx.arc(point1.x, point1.y, cycle_width, 0, Math.PI * 2, true);
ctx.fill();
ctx.closePath(); // 点中间的字——点的序号
ctx.beginPath();
ctx.fillStyle = 'white';
ctx.fillText(point1.index, point1.x, point1.y + cycle_width / 4);
ctx.closePath();
});
},
_renderLine = function(point1, point2, power, ctx) {
ctx = ctx || canvas_context; requestAnimationFrame(function() {
// 点与点间的连线
ctx.beginPath();
ctx.moveTo(point1.x, point1.y);
ctx.lineTo(point2.x, point2.y);
ctx.closePath();
ctx.stroke(); // 点与点间连线的字——权重
ctx.beginPath();
ctx.fillStyle = 'red';
var x1 = Math.min(point1.x, point2.x),
x2 = Math.max(point1.x, point2.x),
y1 = Math.min(point1.y, point2.y),
y2 = Math.max(point1.y, point2.y);
ctx.fillText(power, 0.5 * x2 + 0.5 * x1, 0.5 * y2 + 0.5 * y1);
ctx.closePath();
});
}; var graph = _renderGraph(_matix2graph(_getRandomMatix(9)));
_renderTree(_getMinTree(graph))
})();
</script>
</body> </html>
这里可以在线运行哦：http://www.w3cfuns.com/home.php?mod=space&uid=5446932&do=blog&quickforward=1&id=5398698