JS使用Prim算法和Kruskal算法实现最小生成树

之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法。

一、权重图和最小生成树

权重图:图的边带权重

最小生成树:在连通图的所有生成树中,所有边的权重和最小的生成树

本文使用的图如下:

它的最小生成树如下:

二、邻接矩阵

邻接矩阵:用来表示图的矩阵就是邻接矩阵,其中下标表示顶点,矩阵中的值表示边的权重(或者有无边,方向等)。

本文在构建邻接矩阵时,默认Number.MAX_SAFE_INTEGER表示两个节点之间没有边,Number.MIN_SAFE_INTEGER表示当前节点没有自环。

代码如下:

/**
 * 邻接矩阵
 * 值为顶点与顶点之间边的权值,0表示无自环,一个大数表示无边(比如10000)
 * */
const MAX_INTEGER = Number.MAX_SAFE_INTEGER;//没有的边
const MIN_INTEGER = Number.MIN_SAFE_INTEGER;//没有自环

const matrix= [
  [MIN_INTEGER, 9, 2, MAX_INTEGER, 6],
  [9, MIN_INTEGER, 3, MAX_INTEGER, MAX_INTEGER],
  [2, 3, MIN_INTEGER, 5, MAX_INTEGER],
  [MAX_INTEGER, MAX_INTEGER, 5, MIN_INTEGER, 1],
  [6, MAX_INTEGER, MAX_INTEGER, 1, MIN_INTEGER]
];

这个邻接矩阵表示的图如下:

三、 边的表示

一个边具有权重、起点、重点三个属性,所以可以创建一个类(对象),实现如下:

/**
 * 边对象
 * */
function Edge(begin, end, weight) {
  this.begin = begin;
  this.end = end;
  this.weight = weight;
}

Edge.prototype.getBegin = function () {
  return this.begin;
};
Edge.prototype.getEnd = function () {
  return this.end;
};
Edge.prototype.getWeight = function () {
  return this.weight;
};

/*class Edge {
  constructor(begin, end, weight) {
    this.begin = begin;
    this.end = end;
    this.weight = weight;
  }
  getBegin() {
    return this.begin;
  }
  getEnd() {
    return this.end;
  }
  getWeight() {
    return this.weight;
  }
}*/

PS:JS这门语言没有私有变量的说法,这里写get方法纯粹是模拟一下私有变量。可以不用这么写,可以直接通过属性访问到属性值。

四、Prim算法

将这个算法的文章数不胜数,这里就不细说了。

其大体思路就是:以某顶点为起点,逐步找各顶点上最小权值的相邻边构建最小生成树,同时其邻接点纳入生成树的顶点中,只要保证顶点不重复添加即可。

实现代码如下:

/**
 * Prim算法
 * 以某顶点为起点,逐步找各顶点上最小权值的边构建最小生成树,同时其邻接点纳入生成树的顶点中,只要保证顶点不重复添加即可
 * 使用邻接矩阵即可
 * 优点:适合点少边多的情况
 * @param matrix 邻接矩阵
 * @return Array 最小生成树的边集数组
 * */
function prim(matrix) {
  const rows = matrix.length,
    cols = rows,
    result = [],
    savedNode = [0];//已选择的节点
  let minVex = -1,
    minWeight = MAX_INTEGER;
  for (let i = 0; i < rows; i++) {
    let row = savedNode[i],
      edgeArr = matrix[row];
    for (let j = 0; j < cols; j++) {
      if (edgeArr[j] < minWeight && edgeArr[j] !== MIN_INTEGER) {
        minWeight = edgeArr[j];
        minVex = j;
      }
    }

    //保证所有已保存节点的相邻边都遍历到
    if (savedNode.indexOf(minVex) === -1 && i === savedNode.length - 1) {
      savedNode.push(minVex);
      result.push(new Edge(row, minVex, minWeight));

      //重新在已加入的节点集中找权值最小的边的外部边
      i = -1;
      minWeight = MAX_INTEGER;

      //已加入的边,去掉,下次就不会选这条边了
      matrix[row][minVex] = MAX_INTEGER;
      matrix[minVex][row] = MAX_INTEGER;
    }
  }
  return result;
}

五、Kruskal算法

介绍这个算法的文章也很多,这里不细说。

其主要的思路就是:遍历所有的边,按权值从小到大排序,每次选取当前权值最小的边,只要不构成回环,则加入生成树。

5.1 邻接矩阵转成边集数组

与Prim算法不同,Kruskal算法是从最小权值的边开始的,所以使用边集数组更方便。所以需要将邻接矩阵转成边集数组,并且按照边的权重从小到大排序。

/**
 * 邻接矩阵转边集数组的函数
 * @param matrix 邻接矩阵
 * @return Array 边集数组
 * */
function changeMatrixToEdgeArray(matrix) {
  const rows = matrix.length,
    cols = rows,
    result = [];
  for (let i = 0; i < rows; i++) {
    const row = matrix[i];
    for(let j = 0 ; j < cols; j++) {
      if(row[j] !== MIN_INTEGER && row[j] !== MAX_INTEGER) {
        result.push(new Edge(i, j, row[j]));
        matrix[i][j] = MAX_INTEGER;
        matrix[j][i] = MAX_INTEGER;
      }
    }
  }
  result.sort((a, b) => a.getWeight() - b.getWeight());
  return result;
}

5.2 Kruskal算法的具体实现

Kruskal算法的一个要点就是避免环路,这里采用一个数组来保存已纳入生成树的顶点和边(连线),其下标是边(连线)的起点,下标对应的元素值是边(连线)的终点。下标对应的元素值为0,表示还没有以它为起点的边(连线)。

连线:表示一条或多条边前后连接形成的一条线,这条线没有环路。

/**
 * kruskal算法
 * 遍历所有的边,按权值从小到大排序,每次选取当前权值最小的边,只要不构成回环,则加入生成树
 * 邻接矩阵转换成边集数组
 * 优点:适合点多边少的情况
 * @param matrix 邻接矩阵
 * @return Array 最小生成树的边集数组
 * */
function kruskal(matrix) {
  const edgeArray = changeMatrixToEdgeArray(matrix),
    result = [],
    //使用一个数组保存当前顶点的边的终点,0表示还没有已它为起点的边加入
    savedEdge = new Array(matrix.length).fill(0);

  for (let i = 0, len = edgeArray.length; i < len; i++) {
    const edge = edgeArray[i];
    const n = findEnd(savedEdge, edge.getBegin());
    const m = findEnd(savedEdge, edge.getEnd());
    console.log(savedEdge, n, m);
    //不相等表示这条边没有与现有生成树形成环路
    if (n !== m) {
      result.push(edge);
      //将这条边的结尾顶点加入数组中,表示顶点已在生成树中
      savedEdge[n] = m;
    }
  }
  return result;
}

/**
 * 查找连线顶点的尾部下标
 * @param arr 判断边与边是否形成环路的数组
 * @param start 连线开始的顶点
 * @return Number 连线顶点的尾部下标
 * */
function findEnd(arr, start) {
  //就是一直循环,直到找到终点,如果没有连线,就返回0
  while (arr[start] > 0) {
    start = arr[start];
  }
  return start;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Prim(普里姆)算法求最小生成树的思想及C语言实例讲解

    Prim 算法思想: 从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1,再连接与 T1 最近顶点 v2 构成树 T2, 如此重复直到所有顶点均在所构成树中为止. 最小生成树(MST):权值最小的生成树. 生成树和最小生成树的应用:要连通n个城市需要n-1条边线路.可以把边上的权值解释为线路的造价.则最小生成树表示使其造价最小的生成树. 构造网的最小生成树必须解决下面两个问题: 1.尽可能选取权值小的边,但不能构成回路: 2.选取n-1条恰当的边以连通n个顶点: MST性质:假设G=(V

  • 详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)

    1.最小生成树:无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1 问题背景: 假设要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路.这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网.在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价.n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条,以使总的耗费最少呢? 1.2 分析问题(建立模型): 可以用连通网来表示n个城市以及n个城市间可能设置的通信线

  • 最小生成树算法之Prim算法

    本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程. 1.什么是最小生成树算法? 简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小.这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法. 2.Prim算法的步骤是什么? 这就要涉及一些图论的知识了. a.假定图的顶点集合为V,边集合为E. b.初始化点集合U={u}.//u为V中的任意选定的一点 c.从u的邻接结点中

  • JS使用Prim算法和Kruskal算法实现最小生成树

    之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法. 一.权重图和最小生成树 权重图:图的边带权重 最小生成树:在连通图的所有生成树中,所有边的权重和最小的生成树 本文使用的图如下: 它的最小生成树如下: 二.邻接矩阵 邻接矩阵:用来表示图的矩阵就是邻接矩阵,其中下标表示顶点,矩阵中的值表示边的权重(或者有无边,方向等). 本文在构建邻接矩阵时,默认Number.MAX_SAFE_INTEGER表示两个节点之间没有边,Number.MIN_

  • C++实现查找中位数的O(N)算法和Kmin算法

    本文实例讲述了C++实现查找中位数的O(N)算法和Kmin算法,分享给大家供大家参考.具体方法如下: 利用快速排序的partition操作来完成O(N)时间内的中位数的查找算法如下: #include <iostream> #include <cassert> #include <algorithm> #include <iterator> using namespace std; int array[] = {1, 2, 10, 8, 9, 7, 5};

  • 深入串的模式匹配算法(普通算法和KMP算法)的详解

    串的定位操作通常称作串的模式匹配,是各种处理系统中的最重要操作之一.模式匹配最朴素的算法是回溯法,即模式串跟主串一个字符一个字符的匹配,当模式串中跟主串不匹配时,主串回溯到与模式串匹配开始的下一个位置,模式串回溯到第一个位置,继续匹配.算法的时间复杂度为O(m*n),算法如下: 复制代码 代码如下: //朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替{

  • python实现的二叉树算法和kmp算法实例

    主要是:前序遍历.中序遍历.后序遍历.层级遍历.非递归前序遍历.非递归中序遍历.非递归后序遍历 复制代码 代码如下: #!/usr/bin/env python#-*- coding:utf8 -*- class TreeNode(object):    def __init__(self, data=None, left=None, right=None):        self.data = data        self.left = left        self.right =

  • C#图表算法之最小生成树

    目录 1.原理 1.切分定理 2.贪心算法 2.加权无向图的数据类型 3.最小生成树 API 4.Prim 算法 数据结构 维护横切边的集合 实现 性能 5. Prim 算法的即时实现 6.Kruskal 算法 实现 加权图是一种为每条边关联一个权值或是成本的图模型.这种图能够自然地表示许多应用.在一幅航空图中,边表示航线,权值则可以表示距离或是费用.在这些情形中,最令人感兴趣的自然是将成本最小化.这里用加权无向图模型来解决最小生成树:给定一幅加权无向图,找到它的一棵最小生成树. 图的生成树是它

  • C++使用Kruskal和Prim算法实现最小生成树

    很久以前就学过最小生成树之Kruskal和Prim算法,这两个算法很容易理解,但实现起来并不那么容易.最近学习了并查集算法,得知并查集可以用于实现上述两个算法后,我自己动手实现了最小生成树算法. 宏观上讲,Kruskal算法就是一个合并的过程,而Prim算法是一个吞并的过程,另外在Prim算法中还用到了一种数据结构--优先级队列,用于动态排序.由于这两个算法很容易理解,在此不再赘述.接下来给出我的源代码. 输入 第一行包含两个整数n和m,n表示图中结点个数,m表示图中边的条数:接下来m行,每一行

  • js中scrollTop()方法和scroll()方法用法示例

    本文实例讲述了js中scrollTop()方法和scroll()方法用法.分享给大家供大家参考,具体如下: 设置滚动条据顶部的高度: $("div").scrollTop(100); //把 scroll top offset 设置为 100px 获得滚动条的高度: $("div").scrollTop()://获得 scroll top offset 触发滚动事件 $(selector).scroll() 将函数绑定到滚动事件中: $(selector).scro

  • 基于js 各种排序方法和sort方法的区别(详解)

    今天突发奇想,想明白sort方法是否比各种排序都有优势,所以就参考别人的代码,做了一个测试,结果令人惊讶啊,上代码. <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width,initial-scale=1.0,max

  • C++图论之Bellman-Ford算法和SPFA算法的实现

    目录 Bellman-Ford算法 例题:AcWing 853. 有边数限制的最短路 算法步骤 代码实现 SPFA算法 代码实现 给定一张有向图,若对于图中的某一条边(x,y,z),有dist[y]≤dist[x]+z成立,则称该边满足三角形不等式.如果所有边都满足三角形不等式,则dist数组就是所求的最短路. Bellman-Ford算法 (x,y,z)表示的是一条从 x 出发, 到达 y ,长度为 z 的有向边. 首先介绍基于迭代的Bellman-Ford算法,它的流程如下: 1.扫描所有边

随机推荐