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

本是古典何须时尚 2022-04-03 14:14 174阅读 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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_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，用于表示一条边。以下图为例：

<table> 
 <thead> 
  <tr> 
   <th>lowcost</th> 
   <th>0</th> 
   <th>0</th> 
   <th>18</th> 
   <th>65535</th> 
   <th>26</th> 
   <th>0</th> 
   <th>16</th> 
   <th>65535</th> 
   <th>12</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>adjvex</td> 
   <td>0</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>5</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
  </tr> 
 </tbody> 
</table>

此时表示，边（v0，v1）和（v0，v5）已经入选最小生成树，用边的权值lowcost值等于0标识。边（v1，v2）这条边权值为18，（v5，v4）这条边权值为26，（v1，v6）这条边权值为16，（v1，v8）这条边权值为12，其余顶点对应的边权值为65535（不存在）。整个算法过程就是一步一步填补这个辅助数组的过程，当lowcost中所有顶点的值都为0时，表示已经找到n-1条边，完成了算法。  
![在这里插入图片描述][20181222215753680.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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]

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

由此可见该算法的关键在于如何判定一条边依附的顶点是否落在T中不同的连通分量上，换句话说，就是如果加入了这条边，则判断T中是否形成了环路，若形成了环路，则必须舍弃这条边。因此需要一个辅助数组parents来帮助判断，如图：  
![在这里插入图片描述][20181223135701592.jpg]  
边（V0,V1）和（V0,V2）已经入选最小生成树，对应的数组为：

其中，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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 5]  
由此可见，在Kruskal算法中，若以堆来存放边，则find函数复杂度为O（loge），而外部有一个for循环e次，因此总算法为O（eloge）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]: /images/20220403/b39f1da8c96f43e89a075f85169ad112.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1]: /images/20220403/a89c1342ff944af981c9b0ade58ee5e1.png
[20181222215753680.png]: /images/20220403/a9bb66ad92f9472582a827b9b440e1a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 2]: /images/20220403/a7f3bc98e312451e9af952fd4145b23c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]: /images/20220403/8d05890798a54f92966ef6ea97bad95a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]: /images/20220403/c2bd8abbe55f45689a216bec9ed795c8.png
[20181223135701592.jpg]: /images/20220403/ddbc0031fcce4883b7d19ebd41f47775.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 5]: /images/20220403/cc6928685ab440e9a22db11dfcf3e453.png