js实现prim+优先队列

缺乏、安全感 2022-06-15 02:50 173阅读 0赞

最近在学算法，沉迷于js的我，就想用js敲一敲这个prim算法，至于prim算法具体是什么，怎么回事，大家可以自行搜索，这里只贴上代码和部分注解  
数据是从文件里读出来的所以用了一下node.js，数据格式如下  
7 9  
1 2 28  
1 6 10  
2 7 14  
2 3 16  
6 5 25  
7 5 24  
7 4 18  
3 4 12  
5 4 22

var fs = require('fs')
    var path = require('path');
    var Q = require("q");
    
    var MAX = 100000;
    var dingdian;//顶点数
    var bian;//边数
    var edge = [];//矩阵
    var node = [] // 记录节点
    var addNew = []; //设置顶点是否加入到集合
    
    // 优先队列数据结构
     function PriorityQueue() { 
        var items = [];
        function QueueElement (element, priority){  // {1}
            this.element = element;
            this.priority = priority;
        }
        this.enqueue = function(element, priority){ 
            var queueElement = new QueueElement(element, priority);
            var added = false;
            for (var i=0; i< items.length; i++){
                if (queueElement.priority < items[i].priority){ // {2}
                    items.splice(i,0,queueElement);             // {3}
                    added = true;
                    break; // {4}
                }
            }
            if (!added){
                items.push(queueElement); //{5}
            }
        };
        this.dequeue = function(){ 
            return items.shift();
        };
        this.front = function(){ 
            return items[0];
        };
        this.isEmpty = function(){ 
            return items.length == 0;
        };
        this.size = function(){ 
            return items.length;
        };
    
     }
    var  q = new PriorityQueue(); //创建优先队列
    
    //初始化输入矩阵
    function initRect(length) { 
        for(var i = 1; i<length+1; i++) {
            edge[i] = [];
            for(var j=1; j<length+1;j++) {
                edge[i][j] = MAX;
            }
        }
    }
    
    //读取数据
    function preadFile (file){ 
          var deferred = Q.defer();
          fs.readFile(file,'utf-8', function(err,data){ 
            if(!err){
              deferred.resolve(data);
            }else{
              deferred.reject(err);
            }
          });
            return deferred.promise;
        }
    
    var filein = path.resolve('input.txt')
    
    preadFile(filein).then(function(data){ 
        var arr = data.split(/\r\n/) //回车空行分割读取
        // console.log(arr)
       for(var i=0;i<arr.length;i++) {
            var _arr = arr[i].split(' ');
    
            if(_arr.length === 2) {
                dingdian = parseInt(_arr[0]);
                bian = parseInt(_arr[1])
                initRect(dingdian);//进行初始化
            }else if(_arr.length === 3) { //添加数据到矩阵
                edge[_arr[0]][_arr[1]] = parseInt(_arr[2]);
                edge[_arr[1]][_arr[0]] = parseInt(_arr[2]);
            }else {
                return;
            }
    
       }
            //求值
            var result = prim(dingdian, edge);
            var _arr = [];
            for(key in result) {
                _arr[key] = result[key].priority
            }
            _arr.splice(0,1);
            var max = Math.max.apply(Math, _arr)
            console.log(max)//结果是25
    });
    
    // 开始prim算法 prim([顶点数],[矩阵])
    function prim(dingdian, edge) { 
        for(var i=1; i<dingdian+1; i++) {
            node[i] = {}
            node[i].element = i;
            node[i].priority = MAX;
            addNew[i] = false; //把所有点都设置成没有放入
        }
        // console.log('node',node[1])
        node[1].priority = 0; //从起始点开始找
    
        q.enqueue(node[1].element, node[1].priority)//把权最小的放入队列
        while(!q.isEmpty()) {
            var _q = q.front();
            q.dequeue();
            var flag = _q.element;//
            if(addNew[flag]) {
                continue;
            }
            addNew[flag] = true;
            for(var j=1; j<dingdian+1; j++) {
                if(j!=flag && !addNew[j] && node[j].priority > edge[flag][j]){
                    node[j].priority = edge[flag][j];
                    q.enqueue(node[j].element, node[j].priority)
                }
            }
        }
        return node
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关堆、队列、优先队列底层实现

1、通过ArrayList实现大根堆：堆：有大根堆和小根堆，对于大根堆来说，其左右子元素比根元素小 1）添加操作：首先将它添加到堆的末尾，然后按以下方式建树：将最后一

骑猪看日落/ 2024年02月18日 21:11/ 0 赞/ 50 阅读

相关优先队列

发现一个对优先队列解释挺好的一个网址[点击打开链接][Link 1] [点击打开链接][Link 2] [Link 1]: http://www.cnblogs.

谁践踏了优雅/ 2022年09月25日 07:22/ 0 赞/ 228 阅读

相关优先队列

[点击打开链接][Link 1] include <cstdio> include <cstring> include <algorithm>

柔光的暖阳◎/ 2022年06月17日 05:41/ 0 赞/ 259 阅读

相关 js实现prim+优先队列

最近在学算法，沉迷于js的我，就想用js敲一敲这个prim算法，至于prim算法具体是什么，怎么回事，大家可以自行搜索，这里只贴上代码和部分注解数据是从文件里读出来的所以

缺乏、安全感/ 2022年06月15日 02:50/ 0 赞/ 174 阅读

相关最小生成树之prim算法（优先队列优化）

prim算法适合稠密图，即边数较多而点较少的情况，时间复杂度为n^2，堆优化的情况下，如果点数为m，边数为n，可以达到nlongm，我还是习惯用优先队列写这个算法，思想很简单，

浅浅的花香味﹌/ 2022年06月12日 02:20/ 0 赞/ 347 阅读

相关优先队列

优先队列：顾名思义，首先它是一个队列，但是它强调了“优先”二字，所以，已经不能算是一般意义上的队列了，它的“优先”意指取队首元素时有一定的选择性，即根据元素的属性选择某一项值最

爱被打了一巴掌/ 2022年05月17日 03:37/ 0 赞/ 247 阅读

相关最小优先队列+prim

include <iostream> include <cstdlib> include <queue> using namespa

ゞ浴缸里的玫瑰/ 2022年02月26日 03:44/ 0 赞/ 222 阅读

相关优先队列+prim（待完善）

include <iostream> using namespace std; define max 999; void prim(i

我会带着你远行/ 2022年02月26日 03:38/ 0 赞/ 252 阅读

相关优先队列

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] 优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

爱被打了一巴掌/ 2022年01月17日 02:39/ 0 赞/ 307 阅读

相关优先队列

1 priority_queue<int, vector<int>, cmp > q2; 2 struct cmp{ 3 bool oper

￡神魔★判官ぃ/ 2022年01月07日 06:27/ 0 赞/ 307 阅读