最小生成树-普里姆（Prim）和克鲁斯卡尔（Kruskal）算法JS实现

墨蓝 2023-08-17 16:19 75阅读 0赞

如何在n个顶点，n\*（n-1）/2条边中，筛选出具有n-1条边的，且具有最小代价的连通网呢？这就是最小生成树问题，下面介绍两种算法：

# 1 普里姆（Prim）算法 #

首先建立图的邻接矩阵存储：

class Graph{
        
    	constructor(v,vr){
        
    		let len = v.length
    		this.vexs = [].slice.apply(v);
    		let arcs = [];
    		for (let i=0;i<len;i++){
        
    			arcs[i] = new Array(len);
    			for (let j=0;j<len;j++){
        
    				arcs[i][j] = i===j ? 0 : 65535;
    			}
    		}
    		for (let arc of vr){
        
    			let v1 = v.indexOf(arc[0]);
    			let v2 = v.indexOf(arc[1]);
    			arcs[v1][v2] = arcs[v2][v1] = arc[2] || 1;
    		}
    		this.arcs = arcs;
    	}
    
    }
    
    let a = new Graph(['v0','v1','v2','v3','v4','v5','v6','v7','v8'],[['v0','v1',10],['v0','v5',11],['v1','v6',16],['v1','v2',18],['v1','v8',12],['v6','v7',19],['v5','v6',17],['v4','v5',26],['v3','v4',20],['v3','v7',16],['v2','v8',8],['v3','v8',21],['v4','v7',7],['v2','v3',22],['v3','v6',24]]);
    console.log(a);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]  
算法思路：  
假设N=(P,\{E\})是连通网，TE是N上最小生成树中边的集合。算法从U=\{u0\} (u0∈V)，TE=\{ \}开始。重复执行下述操作：在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0),并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,\{TE\})为N的最小生成树。

为实现该算法，需要设置一个辅助数组closeEdge（长度与图的顶点数相同）用于记录从顶点集U到V-U的代价最小的边。该数组每个元素有两个域，分别为adjvex和lowcost，用于表示一条边。以下图为例：  
![在这里插入图片描述][20190928100100104.png]  
此时表示，边（v0，v1）和（v0，v5）已经入选最小生成树，用边的权值lowcost值等于0标识。边（v1，v2）这条边权值为18，（v5，v4）这条边权值为26，（v1，v6）这条边权值为16，（v1，v8）这条边权值为12，其余顶点对应的边权值为65535（不存在）。整个算法过程就是一步一步填补这个辅助数组的过程，当lowcost中所有顶点的值都为0时，表示已经找到n-1条边，完成了算法。  
![在这里插入图片描述][20190928100126759.png]  
可以根据算法，思考这个问题：

class MiniEdge{
           //定义辅助数组的元素
    	constructor(adjvex,lowcost){
        
    		this.adjvex = adjvex;   //用于表示边
    		this.lowcost = lowcost;   //用于存储边的权值
    	}
    }
    
    function Prim(G){
        
    	let closeEdge = new Array(G.vexs.length);
    	closeEdge[0] = new MiniEdge(0,0);     //将顶点v0加入最小生成树
    	for (let i=1;i<G.vexs.length;i++){
              //初始化数组，此时数组保存着顶点v0到各个顶点的边及权值
    		closeEdge[i] = new MiniEdge(0,G.arcs[0][i]);
    	}
    
    	var j;
    	var miniVex;   //用于存储具有最小权值的边顶点下标
    	var miniCost;   //用于存储最小的权值
    	for (let i=1;i<G.vexs.length;i++){
        
    		j = 1;
    		miniVex = 0;   //初始化
    		miniCost = 65535;
    		while(j<G.vexs.length){
           //找寻最小权值的边，并存储相应的顶点
    			if (closeEdge[j].lowcost !==0 && closeEdge[j].lowcost < miniCost){
          //注意lowcost等于0代表该节点已经入选生成树，应跳过
    				miniCost = closeEdge[j].lowcost;
    				miniVex = j;
    			}
    			j++;
    		}
    
    		console.log(G.vexs[closeEdge[miniVex].adjvex],G.vexs[miniVex],miniCost);  //打印最小权值的边及权值
    
    		closeEdge[miniVex].lowcost = 0;    //将当前顶点加入最小生成树
    		for (j = 1;j<G.vexs.length;j++){
           //更新辅助数组，此时数组保存着最小生成树中顶点到图中其余各顶点权值最小的边
    			if (closeEdge[j].lowcost !==0 && G.arcs[miniVex][j] < closeEdge[j].lowcost){
        
    				closeEdge[j].lowcost = G.arcs[miniVex][j];
    				closeEdge[j].adjvex = miniVex;
    			}
    		}
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]  
由此可见，两个嵌套的循环，Prim算法复杂度为O（n2）

# 2 克鲁斯卡尔（Kruskal）算法 #

Prim算法以顶点为起点，逐步寻找各顶点上最小权值的边来构建最小生成树，而Kruskal算法直接就以边为目标去构造最小生成树。  
**首先需要构建一个边集数组：**

class edge{
        
    	constructor(begin,end,weight){
        
    		this.begin = begin;
    		this.end = end;
    		this.weight = weight;
    	}
    }
    
    class Graph{
        
    	constructor(v,vr){
        
    		let len = v.length;
    		this.vexs = [].slice.apply(v);
    		let edges = [];
    		let v1=0,v2=0;
    		for (let arc of vr){
        
    			v1 = v.indexOf(arc[0]);
    			v2 = v.indexOf(arc[1]);
    			edges.push(new edge(v1,v2,arc[2]));
    		}
    		edges.sort(function(a,b){
        
    			return a.weight - b.weight;
    		})
    		this.edges = edges;
    	}
    }
    
    let a = new Graph(['v0','v1','v2','v3','v4','v5','v6','v7','v8'],[['v0','v1',10],['v0','v5',11],['v1','v6',16],['v1','v2',18],['v1','v8',12],['v6','v7',19],['v5','v6',17],['v4','v5',26],['v3','v4',20],['v3','v7',16],['v2','v8',8],['v3','v8',21],['v4','v7',7],['v2','v3',22],['v3','v6',24]]);
    console.log(a);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 4]  
算法思路：  
假设N=\{V,\{E\}\}是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=\{V,\{ \}\}，图中每个顶点自成一个连通分量，在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。

由此可见该算法的关键在于如何判定一条边依附的顶点是否落在T中不同的连通分量上，换句话说，就是如果加入了这条边，则判断T中是否形成了环路，若形成了环路，则必须舍弃这条边。因此需要一个辅助数组parents来帮助判断，如图：  
![在这里插入图片描述][2019092810033527.png]  
边（V0,V1）和（V0,V2）已经入选最小生成树，对应的数组为：  
![在这里插入图片描述][20190928100355416.png]  
其中，parents\[0\] = 1, parents\[1\] = 2, parents\[2\] = 0，代表此时最小生成树中已包含v0，v1，v2顶点。此时还需添加一条边，由于边（V1，V2）权值较小，因此先试试添加这条边，将这条边的一个顶点序号1代入下列代码，返回2，再将该边的另一个顶点2代入，返回2，我们发现头尾顶点的返回值相等，这表明此时形成了环路，应该舍弃这条边。接着，我们代入边（V1，V3）的两个顶点序号，返回2≠3，因此没有将其纳入最小生成树中。

function(i){
        
    	while (parents[i] >0) i = parents[i];
    	return i;
    }

算法代码很短，很容易理解

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 5]  
由此可见，在Kruskal算法中，若以堆来存放边，则find函数复杂度为O（loge），而外部有一个for循环e次，因此总算法为O（eloge）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]: /images/20230810/f5dcc59a5d9c4ddf869d4d6accd449fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]: /images/20230810/ab4a71fd40a84039b1f7544985f8956b.png
[20190928100100104.png]: /images/20230810/52d6355de1a94a639613b863714afe2d.png
[20190928100126759.png]: /images/20230810/87c2766ebbd242e8907c96a46c97be43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]: /images/20230810/e279c9e3f581414fb0660c5442e851f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 3]: /images/20230810/113e54788ebe4c01b44b64299a638cf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 4]: /images/20230810/aea00825b5654a7dac25e4df5df7eba8.png
[2019092810033527.png]: /images/20230810/a3b751d5048a4e79a7884ded2e6622f7.png
[20190928100355416.png]: /images/20230810/20496d35ff4a436eb7e95450851b6ca3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 5]: /images/20230810/1e4994c71a974041ac9c80c56c8db837.png