数据结构（十）：最小生成树
最小生成树是带权无向连通图中权值最小的生成树，根据 图 中生成树定义可知， 个顶点的连通图中，生成树中边的个数为 ，向生成树中添加任意一条边，则会形成环。生成树存在多种，其中权值之和最小的生成树即为最小生成树。
若 为最小生成树 的一个真子集，即 的顶点集合和边集合都是 的顶点和边集合的子集，构造最小生成树过程为向 中添加顶点和边，添加的原则有两种：
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 算法的总时间复杂度为 。
