漫画:什么是最小生成树?

来自:程序员小灰(微信号:chengxuyuanxiaohui),作者:小灰



—————  第二天  —————






————————————





首先看看第一个例子,有下面这样一个带权图:



它的最小生成树是什么样子呢?下图绿色加粗的边可以把所有顶点连接起来,又保证了边的权值之和最小:



去掉那些多余的边,该图的最小生成树如下:




下面我们再来看一个更加复杂的带权图:



同样道理,下图绿色加粗的边可以把所有顶点连接起来,又保证了边的权值之和最小:




去掉那些多余的边,该图的最小生成树如下:







怎样铺设才能保证成本最低呢?


城市之间的交通网就像一个连通图,我们并不需要在每两个城市之间都直接进行连接,只需要一个最小生成树,保证所有的城市都有铁路可以触达即可。






Prim算法是如何工作的呢?


这个算法是以图的顶点为基础,从一个初始顶点开始,寻找触达其他顶点权值最小的边,并把该顶点加入到已触达顶点的集合中。当全部顶点都加入到集合时,算法的工作就完成了。Prim算法的本质,是基于贪心算法


接下来说一说最小生成树的存储方式。我们最常见的树的存储方式,是链式存储,每一个节点包含若干孩子节点的指针,每一个孩子节点又包含更多孩子节点的指针:



这样的存储结构很清晰,但是也相对麻烦。为了便于操作,我们的最小生成树用一维数组来表达,数组下标所对应的元素,代表该顶点在最小生成树当中的父亲节点。(根节点没有父亲节点,所以元素值是-1)




下面让我们来看一看算法的详细过程:


1.选择初始顶点,加入到已触达顶点集合。




2.从已触达顶点出发,寻找到达新顶点的权值最小的边。显然从0到2的边权值最小,把顶点2加入到已触达顶点集合,Parents当中,下标2对应的父节点是0。



3.从已触达顶点出发,寻找到达新顶点的权值最小的边。显然从2到4的边权值最小,把顶点4加入到已触达顶点集合,Parents当中,下标4对应的父节点是2。



4.从已触达顶点出发,寻找到达新顶点的权值最小的边。显然从0到1的边权值最小,把顶点1加入到已触达顶点集合,Parents当中,下标1对应的父节点是0。



5.从已触达顶点出发,寻找到达新顶点的权值最小的边。显然从1到3的边权值最小,把顶点3加入到已触达顶点集合,Parents当中,下标3对应的父节点是1。



这样一来,所有顶点都加入到了已触达顶点集合,而最小生成树就存储在Parents数组当中。



  1. final static int INF = Integer.MAX_VALUE;



  2. public static int[] prim(int[][] matrix){

  3.    List<Integer> reachedVertexList = new ArrayList<Integer>();


  4.    //选择顶点0为初始顶点,放入已触达顶点集合中

  5.    reachedVertexList.add(0);

  6.    //创建最小生成树数组,首元素设为-1

  7.    int[] parents = new int[matrix.length];

  8.    parents[0] = -1;


  9.    //边的权重

  10.    int weight;

  11.    //源顶点下标

  12.    int fromIndex = 0;

  13.    //目标顶点下标

  14.    int toIndex = 0;


  15.    while (reachedVertexList.size() < matrix.length) {

  16.        weight = INF;

  17.        //在已触达的顶点中,寻找到达新顶点的最短边

  18.        for (Integer vertexIndex : reachedVertexList) {

  19.            for (int i = 0; i < matrix.length; i++) {

  20.                if (!reachedVertexList.contains(i)) {

  21.                    if (matrix[vertexIndex][i] < weight) {

  22.                        fromIndex = vertexIndex;

  23.                        toIndex = i;

  24.                        weight = matrix[vertexIndex][i];

  25.                    }

  26.                }

  27.            }

  28.        }

  29.        //确定了权值最小的目标顶点,放入已触达顶点集合

  30.        reachedVertexList.add(toIndex);

  31.        //放入最小生成树的数组

  32.        parents[toIndex] = fromIndex;

  33.    }


  34.    return parents;

  35. }


  36. public static void main(String[] args) {

  37.    int[][] matrix = new int[][]{

  38.            {0, 4, 3, INF, INF},

  39.            {4, 0, 8, 7, INF},

  40.            {3, 8, 0, INF, 1},

  41.            {INF, 7, INF, 0, 9},

  42.            {INF, INF, 1, 9, 0},

  43.    };

  44.    int[] parents = prim(matrix);

  45.    System.out.println(Arrays.toString(parents));

  46. }


这段代码当中,图的存储方式是邻接矩阵,在main函数中作为测试用例的图和对应的邻接矩阵如下:


当然,也可以使用邻接表来实现prim算法,有兴趣的小伙伴可以尝试写一下代码。





来自:程序员小灰(微信号:chengxuyuanxiaohui),作者:小灰

程序员小灰

推荐↓↓↓
算法与数据结构
上一篇:滑动窗口算法解决子串问题 下一篇:位运算中异或的常见用法总结