image.png
加点法是以一个初始点开始的，而加边法是以最短的边开始的

克鲁斯卡尔算法//加边法

1：选择最短的边进行连接（此处的连接是连接最短边两端的点）
2：要保证连接的两端至少一个点是新的点
3：或者这个边将是两个部分进行连接（可以将已经连接的边看做是一个小部落，可以将两个小部落连接为一个大部落）
4：重复1-3的步骤直到所有的点都连接起来
如上图进行加边法
最短的边 4 也就是AB两点 符合步骤1 将两点连接
第二短的边 5 也就是CD两点 符合步骤1 将两点连接
第三短的边 6 也就是BD两点 符合步骤3 将两点连接
第四短的边 7 也就是 DE 两点 符合步骤2 将两点连接

  1. let max = 999999;
  2. let pointSet = []; //储存点
  3. let distance = [
  4.     [0, 4, 7, max, max],
  5.     [4, 0, 8, 6, max],
  6.     [7, 8, 0, 5, max],
  7.     [max, 6, 5, 0, 7],
  8.     [max, max, max, 7, 0]
  9. ] // 将图的信息储存下来
  11. class Node {
  12.     constructor(value) {
  13.         this.value = value;
  14.         this.neighbor = [];
  15.     }
  16. }
  17. let a = new Node('A');
  18. let b = new Node('B');
  19. let c = new Node('C');
  20. let d = new Node('D');
  21. let e = new Node('E');
  22. pointSet.push(a)
  23. pointSet.push(b)
  24. pointSet.push(c)
  25. pointSet.push(d)
  26. pointSet.push(e)
  27. /**
  28.  * 是否可以连接
  29.  * @param {*} firstMember  第一个部落
  30.  * @param {*} secondMember  第二个部落
  31.  * @param {*} tribeArr  所有的大部落 距离最近的两个部落可以合并成一个大部落，最后所有的部落合成一个部落
  32.  * @returns
  33.  */
  34. function isLink(firstMember, secondMember, tribeArr) {
  35.     let beforePoin = null;
  36.     let endPoin = null;
  38.     // 查看所属部落
  39.     // 当俩个都不属于任何部落进行连接
  40.     // 当其中一个有部落，另一个没可以进行连接
  41.     // 当为一个部落不能进行接连
  42.     // 当两个为同一个部落的话，无法进行连接
  43.     for (let i = 0; i < tribeArr.length; i++) {
  44.         if (tribeArr[i].indexOf(firstMember) > -1) {
  45.             beforePoin = tribeArr[i]
  46.         }
  47.         if (tribeArr[i].indexOf(secondMember) > -1) {
  48.             endPoin = tribeArr[i]
  49.         }
  50.     }
  51.     if (beforePoin!=null && endPoin != null&& beforePoin == endPoin) {
  52.         return false;
  53.     }
  54.     return true;
  55. }
  56. /**
  57.  * 将线两个端连接起来
  58.  * @param {*} firstMember  第一个部落
  59.  * @param {*} secondMember 第二个部落
  60.  * @param {*} tribeArr  所有的大部落 距离最近的两个部落可以合并成一个大部落，最后所有的部落合成一个部落
  61.  */
  62. function link(firstMember, secondMember, tribeArr) {
  63.     let beforePoin = null;
  64.     let endPoin = null;
  65.     // 查看所属部落
  66.     // 当俩个都不属于任何部落进行连接
  67.     // 当其中一个有部落，另一个没可以进行连接
  68.     // 当两个都有部落且部落不相同时可进行连接
  69.     // 当为一个部落不能进行接连
  70.     for (let i = 0; i < tribeArr.length; i++) {
  71.         if (tribeArr[i].indexOf(firstMember) > -1) {
  72.             beforePoin = tribeArr[i]
  73.         }
  74.         if (tribeArr[i].indexOf(secondMember) > -1) {
  75.             endPoin = tribeArr[i]
  76.         }
  77.     }
  78.     if (beforePoin == null && endPoin == null) {
  79.         //当俩个都不属于任何部落 创建一个部落 并将其记录在部落数组中
  80.         let tribe = []
  81.         tribe.push(firstMember)
  82.         tribe.push(secondMember)
  83.         tribeArr.push(tribe)
  84.     } else if (beforePoin != null && endPoin == null) {
  85.         // 当前一个有部落，后一个没部落，将后一个纳入部落
  86.         beforePoin.push(endPoin)
  87.     } else if (beforePoin == null && endPoin != null) {
  88.         // 当后一个有部落，前一个没部落，将第一个纳入部落
  89.         endPoin.push(beforePoin)
  90.     } else if (beforePoin != null && endPoin != null && beforePoin != endPoin) {
  91.         //  当俩个都有部落且部落不一样，将两个部落合并成一个部落
  92.         let newTribe = beforePoin.concat(endPoin)
  93.         let index = tribeArr.indexOf(endPoin)
  94.         tribeArr.splice(index, 1)
  95.         index = tribeArr.indexOf(beforePoin)
  96.         tribeArr.splice(index, 1)
  97.         tribeArr.push(newTribe)
  98.     }
  99.     firstMember.neighbor.push(secondMember)
  100.     secondMember.neighbor.push(firstMember)
  101. }
  102. /**
  103.  * 加边法
  104.  * @param {*} pointSet  所有点的集合
  105.  * @param {*} distance  所有线的集合
  106.  */
  107. function kruskal(pointSet, distance) {
  108.     let tribeArr = []
  110.     while (true) {
  111.         let minDistance = max;
  112.         let begin = null;
  113.         let end = null;
  114.         let nowValue = null;
  115.         for (let i = 0; i < distance.length; i++) {
  116.             for (let j = 0; j < distance[i].length; j++) {
  117.                 nowValue = distance[i][j]
  118.                 let firstMember = pointSet[i]
  119.                 let secondMember = pointSet[j]
  120.                 if (nowValue > 0 && nowValue < minDistance && isLink(firstMember, secondMember, tribeArr)) {
  121.                     minDistance = nowValue;
  122.                     begin = firstMember;
  123.                     end = secondMember;
  125.                 }
  126.             }
  127.         }
  128.         link(begin, end, tribeArr)
  129.         if (tribeArr.length == 1 && tribeArr[0].length == pointSet.length) {
  130.             break;
  131.         }
  132.     }
  134. }
  136. kruskal(pointSet, distance)
  138. console.log(pointSet)