首页 > 代码库 > 好玩的Prim算法
好玩的Prim算法
这段时间学算法，用JS实现了一个Prim，用于在连通图中找出最小树，具体内容、代码解析周末会不上，现在先把源码献上：
1 <!DOCTYPE html> 2 <html charset=‘GB2312‘> 3 4 <head> 5 <title>最小树生成算法</title> 6 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 7 8 <style type="text/css"> 9 body>canvas { 10 border: 1px solid black; 11 padding: 10px; 12 margin: 10px auto; 13 } 14 </style> 15 </head> 16 17 <body> 18 <canvas id="canvas" width="1000px" height="400px"></canvas> 19 <canvas id="sub-canvas" width="1000px" height="400px"></canvas> 20 <script type="text/javascript"> 21 !(function() { 22 var canvas_context = document.getElementById(‘canvas‘).getContext(‘2d‘), 23 sub_ctx = document.getElementById(‘sub-canvas‘).getContext(‘2d‘), 24 _getRandom = function(max, min) { 25 max = max || 100; 26 min = min || 0; 27 return Math.round(Math.random() * (max - min) + min); 28 }, 29 _getRandomMatix = function(nodes) { 30 var matix = [], 31 power = 0, 32 max = 10, 33 min = 0, 34 tmp = 0; 35 for (var i = 0; i < nodes; i++) { 36 for (var j = i; j < nodes; j++) { 37 power = _getRandom(max, min); 38 matix[i] = matix[i] || []; 39 matix[j] = matix[j] || []; 40 tmp = i === j ? 0 : (Math.random() > 0.6 ? 1 : 0) * power; 41 matix[i][j] = matix[j][i] = tmp; 42 } 43 console.log(matix[i].join(‘,‘)) 44 } 45 46 // 构造连通图 47 for (var i = 0; i < matix.length; i++) { 48 var isValid = true; 49 for (var j = 0; j < matix[i].length; j++) { 50 isValid = isValid && matix[i][j] !== 0; 51 } 52 if (!isValid) { 53 var rindex = _getRandom(matix[i].length - 1, 0), 54 v = _getRandom(max, min + 1); 55 matix[i][rindex] = matix[rindex][i] = v; 56 } 57 } 58 return matix; 59 }, 60 _matix2graph = function(matix) { 61 var len = matix.length, 62 row = null, 63 cell = null, 64 graph = {}, 65 x, 66 y; 67 canvas_context.font = cycle_width / 2 + ‘px Arial bold‘; 68 canvas_context.textAlign = ‘center‘; 69 for (var i = 0; i < len; i++) { 70 x = _getRandom(pain_rect.x2, pain_rect.x1); 71 y = _getRandom(pain_rect.y2, pain_rect.y1); 72 73 graph[i] = { 74 x: x, 75 y: y, 76 powers: matix[i] 77 } 78 } 79 return graph; 80 }, 81 _getMinTree = function(graph) { 82 var point1 = graph[0], 83 min_tree = { 84 x: point1.x, 85 y: point1.y, 86 index: 0, 87 sub: [] 88 }, 89 min_x = -1, 90 min_y = -1, 91 min = Number.MAX_VALUE, 92 index_inTree = [0], 93 node = null, 94 _findNode = function(index, roots) { 95 if (roots.length === 0) return null; 96 97 var subRoots = []; 98 for (var i in roots) { 99 if (roots[i].index === index) return roots[i];100 else subRoots = subRoots.concat(roots[i].sub);101 }102 return _findNode(index, subRoots);103 };104 105 for (var k in graph) {106 min_x = -1;107 min_y = -1;108 min = Number.MAX_VALUE;109 for (var i = 0; i < index_inTree.length; i++) {110 point1 = graph[index_inTree[i]];111 for (var j = 1; j < point1.powers.length; j++) {112 if (index_inTree.indexOf(j) >= 0) continue;113 else if (point1.powers[j] > 0 && point1.powers[j] < min) {114 min_x = point1.index;115 min_y = j;116 min = point1.powers[j]117 }118 }119 }120 if (min_x >= 0) {121 index_inTree.push(min_y);122 point1 = graph[min_y];123 node = _findNode(graph[min_x].index, [min_tree]);124 if ( !! node) node.sub.push({125 x: point1.x,126 y: point1.y,127 index: min_y,128 power: min,129 sub: []130 });131 }132 console.log(‘min tree node count: ‘ + index_inTree.length + ‘ ; ‘ + node);133 }134 return min_tree;135 },136 canva_width = 1000,137 canva_height = 400,138 x_range = 490,139 y_range = 190,140 pain_rect = {141 x1: canva_width / 2 - x_range,142 x2: canva_width / 2 + x_range,143 y1: canva_height / 2 - y_range,144 y2: canva_height / 2 + y_range145 },146 cycle_width = 10,147 _renderGraph = function(graph) {148 var point1,149 point2,150 count = 0;151 for (var i in graph) {152 point1 = graph[i];153 i = i - 0;154 point1.index = i;155 for (var j = 0; j < point1.powers.length; j++) {156 point2 = graph[j];157 point2.index = j;158 159 _renderPoint(point1);160 _renderPoint(point2);161 if ( !! point1.powers[j]) {162 _renderLine(point1, point2, point1.powers[j]);163 console.log(‘graph ‘ + i + ‘ to ‘ + j + ‘: ‘ + point1.powers[j]);164 count += point1.powers[j];165 }166 }167 }168 console.log(‘end graph :‘ + count);169 return graph;170 },171 _renderTree = function(tree) {172 var _count = 0,173 _renderer = function(root) {174 var point1 = root,175 point2 = null;176 _renderPoint(point1, sub_ctx);177 for (var i = 0; i < root.sub.length; i++) {178 point2 = root.sub[i];179 _renderLine(point1, point2, point2.power, sub_ctx);180 _renderer(point2);181 _count += point2.power;182 console.log(‘tree ‘ + point1.index + ‘ to ‘ + point2.index + ‘ : ‘ + point2.power);183 }184 };185 _renderer(tree);186 187 console.log(‘end tree :‘ + _count)188 },189 _renderPoint = function(point1, ctx) {190 ctx = ctx || canvas_context;191 requestAnimationFrame(function() {192 // 画点193 ctx.beginPath();194 ctx.fillStyle = ‘red‘;195 ctx.arc(point1.x, point1.y, cycle_width, 0, Math.PI * 2, true);196 ctx.fill();197 ctx.closePath();198 199 // 点中间的字——点的序号200 ctx.beginPath();201 ctx.fillStyle = ‘white‘;202 ctx.fillText(point1.index, point1.x, point1.y + cycle_width / 4);203 ctx.closePath();204 });205 },206 _renderLine = function(point1, point2, power, ctx) {207 ctx = ctx || canvas_context;208 209 requestAnimationFrame(function() {210 // 点与点间的连线211 ctx.beginPath();212 ctx.moveTo(point1.x, point1.y);213 ctx.lineTo(point2.x, point2.y);214 ctx.closePath();215 ctx.stroke();216 217 // 点与点间连线的字——权重218 ctx.beginPath();219 ctx.fillStyle = ‘red‘;220 var x1 = Math.min(point1.x, point2.x),221 x2 = Math.max(point1.x, point2.x),222 y1 = Math.min(point1.y, point2.y),223 y2 = Math.max(point1.y, point2.y);224 ctx.fillText(power, 0.5 * x2 + 0.5 * x1, 0.5 * y2 + 0.5 * y1);225 ctx.closePath();226 });227 };228 229 var graph = _renderGraph(_matix2graph(_getRandomMatix(9)));230 _renderTree(_getMinTree(graph))231 })();232 </script>233 </body>234 235 </html>
这里可以在线运行哦：http://www.w3cfuns.com/home.php?mod=space&uid=5446932&do=blog&quickforward=1&id=5398698
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。