JavaScript Kruskal 最小生成树 (MST) 算法（Kruskal’s Minimum Spanning Tree (MST) Algorithm）

         对于加权、连通、无向图，最小生成树(MST) 或最小权重生成树是权重小于或等于其他所有生成树权重的生成树。

Kruskal算法简介：
        在这里，我们将讨论Kruskal 算法来查找给定加权图的 MST。 

        在 Kruskal 算法中，按升序对给定图的所有边进行排序。然后，如果新添加的边不形成循环，它会继续在 MST 中添加新边和节点。它首先选择最小权重边，最后选择最大权重边。因此，我们可以说它在每一步中都做出局部最优选择以找到最优解。因此，这是一种贪婪算法。

如何使用 Kruskal 算法查找 MST？
以下是使用 Kruskal 算法查找 MST 的步骤：

1.按照权重的非递减顺序对所有边进行排序。 
2.选择最小的边。检查它是否与目前形成的生成树形成一个循环。如果没有形成循环，则包括这条边。否则，丢弃它。 
3.重复步骤#2，直到生成树中有 (V-1) 条边。

第 2 步使用并查集算法来检测循环。 
因此，我们建议先阅读以下文章：

并查表算法 | 集合 1（检测图中的循环） 

javascript 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524938

C# 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524824

python 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524698

java 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524698

c++ 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142523025

并查集算法 | 集合 2（按秩并集和路径压缩）

c语言 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526674

javascript 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526517

C# 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526449

python 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526387

java 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526336

c++ 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142525945

        Kruskal 寻找最小成本生成树的算法采用贪婪方法。贪婪选择是选择迄今为止构建的 MST 中不会引起循环的最小权重边。让我们通过一个例子来理解它：

插图：
下面是上述方法的说明：

输入图：

该图包含 9 个顶点和 14 条边。因此，形成的最小生成树将具有 (9 - 1) = 8 条边。 

排序后： 

现在从排序的边列表中逐一选择所有边 

步骤 1：选取边 7-6。未形成循环，将其包括在内。

步骤 2：拾取边 8-2。未形成循环，将其包括在内。    

步骤 3：选取边 6-5。未形成循环，将其包括在内。  

步骤 4：选取边 0-1。没有形成循环，将其包括在内。  

步骤 5：选取边 2-5。未形成循环，将其包括在内。 

步骤 6：选择边 8-6。由于包含此边会导致循环，因此将其丢弃。选择边 2-3：未形成循环，因此将其包括在内。 

步骤 7：选择边 7-8。由于包含此边会导致循环，因此将其丢弃。选择边 0-7。未形成循环，因此将其包括在内。   

步骤 8：选择边 1-2。由于包含此边会导致循环，因此将其丢弃。选择边 3-4。未形成循环，因此将其包括在内。 

注意：由于MST中包含的边数等于（V-1），因此算法在此停止

下面是上述方法的实现： 

// JavaScript implementation of the krushkal's algorithm.  
  
function makeSet(parent,rank,n) 
{ 
    for(let i=0;i<n;i++) 
    { 
        parent[i]=i; 
        rank[i]=0; 
    } 
} 
  
function findParent(parent,component) 
{ 
    if(parent[component]==component) 
        return component; 
  
    return parent[component] = findParent(parent,parent[component]); 
} 
  
function unionSet(u, v, parent, rank,n) 
{ 
    //this function unions two set on the basis of rank 
    //as shown below 
    u=findParent(parent,u); 
    v=findParent(parent,v); 
  
    if(rank[u]<rank[v]) 
    { 
        parent[u]=v; 
    } 
    else if(rank[u]<rank[v]) 
    { 
        parent[v]=u; 
    } 
    else
    { 
        parent[v]=u; 
        rank[u]++;//since the rank increases if the ranks of two sets are same 
    } 
} 
  
function kruskalAlgo(n, edge) 
{ 
    //First we sort the edge array in ascending order 
    //so that we can access minimum distances/cost 
    edge.sort((a, b)=>{ 
        return a[2] - b[2]; 
    }) 
    //inbuilt quick sort function comes with stdlib.h 
    //go to https://www.geeksforgeeks.org/comparator-function-of-qsort-in-c/ 
    //if there is any doubt regarding the function 
    let parent = new Array(n); 
    let rank = new Array(n); 
  
    makeSet(parent,rank,n);//function to initialize parent[] and rank[] 
  
    let minCost=0;//to store the minimun cost 
  
    document.write("Following are the edges in the constructed MST"); 
    for(let i=0;i<n;i++) 
    { 
        let v1=findParent(parent,edge[i][0]); 
        let v2=findParent(parent,edge[i][1]); 
        let wt=edge[i][2]; 
  
        if(v1!=v2)//if the parents are different that means they are in 
                  //different sets so union them 
        { 
            unionSet(v1,v2,parent,rank,n); 
            minCost+=wt; 
            document.write(edge[i][0] + " -- " + edge[i][1] + " == " + wt); 
        } 
    } 
  
    document.write("Minimum Cost Spanning Tree:",minCost); 
} 
  
  
//Here 5 is the number of edges, can be asked from the user 
//when making the graph through user input 
//3 represents the no of index positions for storing u --> v(adjacent vertices)  
//and its cost/distance; 
let edge = [ 
        [0,1,10], 
        [0,2,6], 
        [0,3,5], 
        [1,3,15], 
        [2,3,4] 
]; 
  
kruskalAlgo(5,edge); 
  
// The code is contributed by Arushi Jindal.   

输出

以下是构建的 MST 中的边
2 -- 3 == 4 
0 -- 3 == 5 
0 -- 1 == 10

最小成本生成树：19

时间复杂度： O（E * logE）或O（E * logV） 

    1.边的排序需要 O(E * logE) 时间。 

    2.排序后，我们遍历所有边并应用查找并集算法。查找和并集操作最多需要 O(logV) 时间。

    3.因此总体复杂度为 O(E * logE + E * logV) 时间。 

    4.E 的值最多为 O(V 2 )，因此 O(logV) 和 O(logE) 相同。因此，总体时间复杂度为 O(E * logE) 或 O(E*logV)

辅助空间： O（V + E），其中 V 是图中顶点的数量，E 是边的数量。