最小生成树算法
最小生成树算法的作用是将一个图的多余边去除,使得图中所有顶点满足连通性的同时,边的权重总和最小,此时这个取出多余边的图我们称为最小连通子图,最小连通子图没有回路,因此是一个树形结构,又称为最小生成树。
如果我们将每条边看成是一个顶点到达另一个顶点的成本,最小生成树算法的目的是将整个图所有节点连通的成本最小化。而最短路径算法则是算出任意两个节点连通的最小成本。
例如一个图原本的样子是这样
变成最小生成树后是这样
最小生成树算法采用贪心算法:
1、创建一个“已连通集合(已触达顶点集合)”用于存放已经遍历过并且加入到生成树的顶点。创建一个一维数组arr表示最小生成树,顶点 i 的父节点为 arr[i]。生成树arr有一个虚拟根节点 -1。
2、从图中任意选择一个顶点A加入到“已连通集合”,节点A作为 arr 的下标0,arr[0] = -1,即顶点A的父节点是虚拟节点 -1。
3、从“已连通集合”中选择一个from节点,要求from节点和from的未访问过的相邻节点to节点的距离最小。将to顶点加入到“已连通集合”和最小生成树中。
4、重复上述过程,直到原图的所有顶点都加入到“已连通集合”和最小生成树中。
所生成的最小生成树的边的条数 = 总顶点数 - 1 = n - 1
代码实现如下: