1、生成树和最小生成树的概念如果图G(V,E)是连通的，那么生成树：包含图G(V,E)中所有节点和|V|-1条边的连通图，一个图的生成树可以有多个最小生成树：最小权重生成树，给生成树的概念增加一个限制，即生成树所有边的权重和最小的树，最小生成树也可以有多个2.求最小生成树的一般方法由于最小生成树包含了图G的所有边，我们只需要找到最小生成树的边集A即可。假设：边集A是图G的任意最小生成树。边的子集，初始A为空。当A不等于G的最小生成树的所有边集M时，通过以下步骤循环找到一条属于M但不属于A的边，并将其加入到A中。现在的问题是我们如何找到它？寻找只属于M而不属于A的边v的方法。当A为空时，图G(V,A)是森林|V|树。当A中有n条边，n<|V|-1时，图G是一个有|V|-(n+1)棵树的森林，加上我们要找的边v，就会得到森林的数量图G中减去1条边v就是这样一条边边v两端的节点属于两棵不同的树。边v的权重是上述所有条件中最小的。3.Kruskal和Prim算法Kruskal和Prim算法是两种常用的最小生成树算法。该算法是上述一般方法的细化，不同之处在于求边v的方法有所不同，Kruskal算法也称为（边扩展）算法，适用于具有稀疏边，Prim算法称为（节点扩展算法），适用于边密集图4.Kruskal算法4.1.Kruskal算法的概念是上面A中的边可以属于多棵不同的树4.2。辅助函数MakeSet(x)MakeSet操作创建一棵包含|V|的树的集合，每棵树只包含一个节点，我们需要给每个节点x添加两个属性varMakeSet=(function(){letset=newSet();returnfunction(x){x.parent=x;x.rank=0;if(!set.has(x))set.add(x);返回集合;}})();4.3.辅助函数Find(x)查找并返回x节点所在的树根节点用于判断两个节点是否在同一棵树中，即是否相交functionFind(x){if(x.父母!=x)x.parent=Find(x.parent);返回x.parent;}4.4。辅助函数Union(u,v)Union函数是为了合并两个节点而设计的，这里的合并要将图G中的连通区域分开。我们通过不断调用union来改变MakeSet集合中元素的连通性，被合并的两个节点会变成一个数。当然读者也可以实现自己的Union。你可以随意，只要你调用Union操作后，MakeSet就改变了，中间图的连通性，没错，u和v节点在同一棵树上。这篇文章的Union方法的思路是按秩（rankrank）合并，路径压缩。这样创建的树节点分布会比较均匀均衡，运行效率高functionUnion(u,v){letuRoot=Find(u);让vRoot=Find(v);//如果u和v在同一棵树中if(uRoot==vRoot)return;//如果u和v不在同一棵树上，则合并它们//如果uRoot的层次小于vRoot的层次，则使用uRoot作为vRoot的前驱节点if(uRoot.rankvRoot.rank)vRoot.parent=uRoot;//设置uRoot为根节点，并在uRoot的层次上加1else{vRoot.parent=uRoot;uRoot.rank=uRoot.rank+1;}}4.5。Kruskal算法Kruskal算法的目的是找出哪些边包含在最小代数中，而在后面的完整代码中，这个函数的实现会有所不同，这里重点介绍原理functionKruskal(G,w){让A=[];//A用于存放最小生成数包含的边for(letxofG.V){make设置（x）；}//按照边的权值从小到大对G.E进行排序for(leteofG.E){quickSort(0,G.E.length-1,G.E,'w');}//由于边已经按照从小到大的顺序有序了，所以这里只需要找到不相交的边（边所在的树是不相交的），for(leteofG.E){if(Find(e.u)!=Find(e.v)){A.push(e);联盟（e.u，e.v）；//改变连通性}}returnA;}4.6.图、顶点、边、数据结构这里的数据结构和如何建图参考BFS、DFS算法原理和js实现，这里不详述//Vertex数据结构functionVertex(){if(!(thisinstanceofVertex))返回新的顶点();this.edges=null;//顶点发出的所有边this.id=null;//节点的唯一标识this.data=null;//存储节点的数据}//数据结构邻接链表-edgefunctionEdge(){if(!(thisinstanceofEdge))returnnewEdge();这个.index=null；//附边的节点的位置this.sibling=null;这个.w=null;//保存边的权重}//数据结构图-GfunctionGraph(){if(!(thisinstanceofGraph))returnnewGraph();这个.V=[];//节点设置this.E=[];//边缘设置this.refer=newMap();//字典用来映射标记节点标识符和数组中的位置}Graph.prototype={constructor:Graph,//这里添加的已经有了边关系//创建图节点initVertex:function(vertexs){//创建节点并初始化节点属性idfor(letvofvertexs){letvertex=Vertex();vertex.id=v.id;this.V.push（顶点）；}//初始化字典for(letiinthis.V){this.refer.set(this.V[i].id,i);}},//建立图中的边关系initEdge:(function(){//创建一个链表并返回链表的第一个节点functioncreateLink(index,len,edges,refer){if(index>=len)returnnull;letedgeNode=Edge();edgeNode.index=refer.get(edges[index].id);//边连接的节点在数组中的位置表示参考字典edgeNode.w=edges[index].w;//边的权重edgeNode.sibling=createLink(++index,len,edges,refer);//通过递归回溯returnedgeNode;}returnfunction(edges){for(letfieldinedges){letindex=this.refer.get(field);//从字典表中查找节点在V中的位置letvertex=this.V[index];//获取节点vertex.edges=createLink(0,edges[field].length,edges[field],this.refer);}}}()),storageEdge:function(edges){this.E=edges;}}varvertexs=[{id:'a'},{id:'b'},{id:'c'},{id:'d'},{id:'e'}];varedges=[{u:'a',v:'b',w:3},{u:'a',v:'c',w:1},{u:'b',v:'a',w:3},{u:'b',v:'c',w:4},{u:'b',v:'d',w:5},{u:'c',v:'a',w:1},{u:'c',v:'b',w:4},{u:'c',v:'d',w:6},{u:'c',v:'e',w:7},{u:'d',v:'b',w:5},{u:'d',v:'c',w:6},{u:'d',v:'e',w:2},{u:'e',v:'c',w:7},{u:'e',v:'d',w:6}]varg=Graph();g.initVertex(vertexs);g.storageEdge(edges);运行这部分代码，生成Kruskal算法输入的图4.7。完整代码和测试算法的输入图片就是上图，红色的边是最终最小生成树包含的边，出现的顺序是ac,de,ab,bd。这里的输入图是一个无向图//快速排序数组a由对象组成，key为排序的参考索引quickSort(0,a.length-1,a,'key')functionquickSort(left,right,a,key){if(left>right)return;变量i=左；varj=正确的；varbenchMark=a[i];可变温度；while(i!=j){//移动jwhile(a[j][key]>=benchMark[key]&&ivRoot.rank)vRoot.parent=uRoot;//选择一个作为根节点else{vRoot.parent=uRoot;uRoot.rank=uRoot.rank+1;}}functionKruskal(G){让A=[];//A用于存放最小生成数包含的边for(letxofG.V){MakeSet(x);}//按照边的权重从小到大对G.E进行排序for(leteofG.E){quickSort(0,G.E.length-1,G.E,'w');}for(leteofG.E){letu=G.V[G.refer.get(e.u)];让v=G.V[G.refer.get(e.v)];if(Find(u)!=Find(v)){A.push(e);联盟（u，v）；}}returnA;}functionVertex(){if(!(thisinstanceofVertex))returnnewVertex();}this.edges=null;//从顶点开始的所有边this.id=null;//节点的唯一标识this.data=null;//存储节点的数据}//数据结构邻接链表-edgefunctionEdge(){if(!(thisinstanceofEdge))returnnew边（）；这个。索引=空；//附边的节点的位置this.sibling=null;这个.w=null;//保存边的权重}//数据结构图-GfunctionGraph(){if(!(thisinstanceofGraph))returnnewGraph();这个.V=[];//节点设置this.E=[];this.refer=newMap();//映射的字典节点的标识和在数组中的位置}Graph.prototype={constructor:Graph,//这里添加的关系已经有了边关系//创建图的节点initVertex:function(vertexs){//创建一个节点并初始化它节点属性idfor(letvofvertexs){letvertex=Vertex();vertex.id=v.id;this.V.push(vertex);}//初始化字典for(letiinthis.V){this.refer.set(this.V[i].id,i);}},//建立图中的边关系initEdge:(function(){//创建一个链表并返回链表的第一个节点functioncreateLink(index,len,edges,refer){if(index>=len)returnnull;letedgeNode=Edge();edgeNode.index=refer.get(edges[index].id);//使用边连接的节点在数组中的位置指的是字典edgeNode.w=edges[索引].w;//边权重edgeNode.sibling=createLink(++index,len,edges,refer);//通过递归回溯returnedgeNode;}returnfunction(edges){for(letfieldinedges){letindex=this.refer.get(field);//从字典表中找出节点在V中的位置letvertex=this.V[index];//获取节点vertex.edges=createLink(0,edges[field].length,edges[field],this.refer);}}}()),storageEdge:function(edges){this.E=edges;}}//测试数据varvertexs=[{id:'a'},{id:'b'},{id:'c'},{id:'d'},{id:'e'}];varedges=[{u:'a',v:'b',w:3},{u:'a',v:'c',w:1},{u:'b',v:'a',w:3},{u:'b',v:'c',w:4},{u:'b',v:'d',w:5},{u:'c',v:'a',w:1},{u:'c',v:'b',w:4},{u:'c',v:'d',w:6},{u:'c',v:'e',w:7},{u:'d',v:'b',w:5},{u:'d',v:'c',w:6},{u:'d',v:'e',w:2},{u:'e',v:'c',w:7},{u:'e',v:'d',w:6}]varg=Graph();g.initVertex(vertexs);g.storageEdge(边缘）；varA=Kruskal（g）；console.log（A）；
