在JavaScript中，求取最小生成树（MinimumSpanningTree,MST）最常用的算法是Prim算法和Kruskal算法。这里我将提供一个基于Kruskal算法的JavaScript实现。
首先，定义一个用于存储图的数据结构，这里使用JavaScript的类来实现：
classGraph{
constructor(vertices){
this.V=vertices;
this.graph=[];
}
addEdge(u,v,w){
this.graph.push([u,v,w]);
}
kruskalMST(){
letresult=[];
this.graph=this.graph.sort((a,b)=>a[2]-b[2]);
letparent=Array(this.V).fill(0);
letrank=Array(this.V).fill(0);
for(leti=0;i
parent[i]=i;
rank[i]=0;
}
lete=0;
for(leti=0;i
letu=this.graph[i][0];
letv=this.graph[i][1];
letw=this.graph[i][2];
letx=this.find(parent,u);
lety服务器托管网=this.find(parent,v);
if(x!==y){
e++;
result.push([u,v,w]);
this.union(parent,rank,x,y);
}
}
returnresult;
}
find(parent,i){
if(parent[i]===i){
returni;
}
returnthis.find(parent,parent[i]);
}
union(parent,rank,x,y){
letxroot=this.find(parent,x);
letyroot=this.find(parent,y);
if(rank[xroot]
parent[xroot]=yroot;
}elseif(rank[xroot]>rank[yroot]){
parent[yroot]=xroot;
}else{
parent[yroot]=xroot;
rank[xroot]++;
}
}
}
然后，你可以像下面这样使用这个类来创建一个图并求出其最小生成树：
letg=newGraph(4);
g.addEdge(0,1,10);
g.addEdge(0,2,6);
g.addEdge(0,3,5);
g.addEdge(1,3,15);
g.addEdge(2,3,4);
letresult=g.kruskalMST();
console.log(“EdgesintheconstructedMST”);
for(leti=0;i
le服务器托管网tu=result[i][0];
letv=result[i][1];
letweight=result[i][2];
console.log(`${u}–${v}==${weight}`);
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 云端聚首，造炬成阳 | 瑞技荣获思科云CCC合作伙伴授牌
共谱云网未来 云端聚首，造炬成阳 首届思科云俱乐部闭门精英堂，今日在苏州尼盛万丽酒店精彩开启。 思科携手神州数码，联袂众多云端创新合作伙伴，同台共聚，共赴云端盛会。 思科与合作伙伴们共同探讨多云架构态势下的机遇和挑战，携手构筑更加智能、安全和优质的云生态。 来…
