数据结构(十):最小生成树
最小生成树是带权无向连通图中权值最小的生成树,根据 图 中生成树定义可知, 个顶点的连通图中,生成树中边的个数为 ,向生成树中添加任意一条边,则会形成环。生成树存在多种,其中权值之和最小的生成树即为最小生成树。
若 为最小生成树 的一个真子集,即 的顶点集合和边集合都是 的顶点和边集合的子集,构造最小生成树过程为向 中添加顶点和边,添加的原则有两种:
kruskal 算法即为上述第一种原则,通过选择图中的最小权值边来构造最小生成树,过程中需要注意避免形成环。
step 1:
最小权值边为顶点 7、8 形成的边
step 2:
最小权值边为顶点 3、9 形成的边
step 3:
最小权值边为顶点 6、7 形成的边
step 4:
最小权值边为顶点 3、6 形成的边
step 5:
最小权值边为顶点 1、2 形成的边
step 6:
最小权值边为顶点 3、4 形成的边
step 7:
最小权值边为顶点 1、8 形成的边
step 8:
最小权值边为顶点 4、5 形成的边
最小生成树的权值之和为 37
这里使用邻接表作为图的存储结构
这里使用 getEdgesFromAdjacencyList 函数完成邻接表到边集合的转换,使用快排 sort 完成对边集合的排序,使用 origin 函数返回每个子图的根。
该函数返回顶点 index 所属子图的根顶点,其中 vertices[index] 位置上存储的是顶点 index 的上一个顶点,每个子图中,根顶点的上一个顶点为自身。
kruskal 算法中使用 getEdgesFromAdjacencyList 函数完成邻接表向边集合的转换,函数内部存在两层循环,访问邻接表中每个顶点的相邻顶点,复杂度为 。使用快排对边集合进行排序,时间复杂度为 ,因为 ,所以快排时间复杂度可以表述为 。 kruskal 算法中 while 循环取最小权值边,并对边的两个顶点执行 origin 函数判断是否属于同一个子图,时间复杂度为 。所以 kruskal 算法的时间复杂度为 。
kruskal 算法的过程为不断对子图进行合并,直到形成最终的最小生成树。 prim 算法的过程则是只存在一个子图,不断选择顶点加入到该子图中,即通过对子图进行扩张,直到形成最终的最小生成树。
step 1:
距离子图的最近顶点为 4
step 2:
距离子图的最近顶点为 3
step 3:
距离子图的最近顶点为 9
step 4:
距离子图的最近顶点为 6
step 5:
距离子图的最近顶点为 7
step 6:
距离子图的最近顶点为 8
step 7:
距离子图的最近顶点为 2
step 8:
距离子图的最近顶点为 1
最小生成树的权值之和为 37
这里使用邻接表作为图的存储结构
这里使用 vertices 列表存储每个顶点元素,每个元素包括两个属性, index 为顶点下标, weight 为顶点距离子图的大小。算法中使用 verticesIndex 列表存储每个顶点元素在 vertices 列表中的下标位置。使用 heapSort 堆排序对每个顶点到子图的距离进行排序,即对 vertices 列表进行排序,使用堆排序内的 transformToHeap 函数调整 vertices 列表为小顶堆。当添加新顶点到子图后,使用 updateVertices 函数完成对相邻顶点的距离更新。
当 vertices 列表调整为小顶堆之后,将列表首、尾元素交换,则列表尾元素即为距离子图最近的顶点元素。
对每一个相邻顶点,如果不在子图中,则判断是否更新到子图的距离。更新距离后的 while 循环操作,目的为调整堆结构为小顶堆。
prim 算法中构造顶点列表的时间复杂度为 。使用堆排序对顶点列表进行排序,时间复杂度为 。 prim 算法中 while 循环取最近顶点元素,并调整元素取出后列表的堆结构,所以调整复杂度为 ;同时,循环结构内执行 updateVertices 函数,更新每个取出顶点的相邻顶点距离值,所以更新顶点数为 ,因为每个顶点更新距离后,需要调整堆结构为小顶堆,所以更新复杂度为 。所以 prim 算法的总时间复杂度为 。