漫画：什么是图的最小生成树？

快来打我* 2023-07-17 11:28 21阅读 0赞

![format_png][]

![format_png 1][]

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

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

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

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

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

![format_png 15][]

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

![format_png 16][]

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

![format_png 17][]

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

![format_png 18][]

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

![format_png 19][]

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

![format_png 20][]

![format_png 21][]

![format_png 22][]

![format_png 23][]

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

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

![format_png 24][]

![format_png 25][]

![format_png 26][]

Prim算法是如何工作的呢？

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

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

![format_png 20][]

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

![format_png 27][]

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

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

![format_png 28][]

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

![format_png 29][]

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

![format_png 30][]

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

![format_png 31][]

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

![format_png 32][]

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

![format_png 33][]

![format_png 34][]

final static int INF = Integer.MAX_VALUE;
    
    
    
    
    
    public static int[] prim(int[][] matrix){
    
    List<Integer> reachedVertexList = new ArrayList<Integer>();
    
    
    
    //选择顶点0为初始顶点，放入已触达顶点集合中
    
    reachedVertexList.add(0);
    
    //创建最小生成树数组，首元素设为-1
    
    int[] parents = new int[matrix.length];
    
    parents[0] = -1;
    
    
    
    //边的权重
    
    int weight;
    
    //源顶点下标
    
    int fromIndex = 0;
    
    //目标顶点下标
    
    int toIndex = 0;
    
    
    
    while (reachedVertexList.size() < matrix.length) {
    
    weight = INF;
    
    //在已触达的顶点中，寻找到达新顶点的最短边
    
    for (Integer vertexIndex : reachedVertexList) {
    
    for (int i = 0; i < matrix.length; i++) {
    
    if (!reachedVertexList.contains(i)) {
    
    if (matrix[vertexIndex][i] < weight) {
    
    fromIndex = vertexIndex;
    
    toIndex = i;
    
    weight = matrix[vertexIndex][i];
    
    }
    
    }
    
    }
    
    }
    
    //确定了权值最小的目标顶点，放入已触达顶点集合
    
    reachedVertexList.add(toIndex);
    
    //放入最小生成树的数组
    
    parents[toIndex] = fromIndex;
    
    }
    
    
    
    return parents;
    
    }
    
    
    
    
    
    public static void main(String[] args) {
    
    int[][] matrix = new int[][]{
    
    {0, 4, 3, INF, INF},
    
    {4, 0, 8, 7, INF},
    
    {3, 8, 0, INF, 1},
    
    {INF, 7, INF, 0, 9},
    
    {INF, INF, 1, 9, 0},
    
    };
    
    int[] parents = prim(matrix);
    
    System.out.println(Arrays.toString(parents));
    
    }

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

![format_png 35][]

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

![format_png 36][]

![format_png 37][]

—————END—————

[format_png]: /images/20230528/04c30f6e9ba04076920a237bfdcbb6f7.png
[format_png 1]: /images/20230528/3b2a05f0f40140eb990ee207297e3e4e.png
[format_png 2]: /images/20230528/dfff81cf563b4e959004e8d7a55ce876.png
[format_png 3]: /images/20230528/03b3c89900dd4de5906c387962f9ce00.png
[format_png 4]: /images/20230528/3d6b5b9546ab4777a72904b30b8252a8.png
[format_png 5]: /images/20230528/205c139d54ba45679eae4182290897f9.png
[format_png 6]: /images/20230528/ae46434da68e4c9b86ec6877f6522a64.png
[format_png 7]: /images/20230528/6e473fdce8394f9cbfadb8cd9b9918ab.png
[format_png 8]: /images/20230528/d1d684912a1c47ad91ca1c91e3392cbd.png
[format_png 9]: /images/20230528/90e14aa148ac450b9d46ec7f2146ebdc.png
[format_png 10]: /images/20230528/f5a1873ea7c84e429e96aec70eb4a48a.png
[format_png 11]: /images/20230528/4fdb106a256e4678a35c543d05e3032f.png
[format_png 12]: /images/20230528/69e403a9174f4ce3ab223615254c6d23.png
[format_png 13]: /images/20230528/74a08185e6a640ffacd06f8d756a8a30.png
[format_png 14]: /images/20230528/eceab6cd05bf441fbc9c3a57c205e30a.png
[format_png 15]: /images/20230528/f0844dd037d3420ba076bd38af5c9056.png
[format_png 16]: /images/20230528/690d161665bc441d84c61cbc368c47ae.png
[format_png 17]: /images/20230528/82ba1e96cfa8417db737a071a683288a.png
[format_png 18]: /images/20230528/341ea1dbf9b243bda3aec443eaaed054.png
[format_png 19]: /images/20230528/5e58260c21994e07918d928f0ccae5e2.png
[format_png 20]: /images/20230528/496df4cb53f24cd59b0b05db3c8f6a01.png
[format_png 21]: /images/20230528/0998b4cb01724943912aab836012935d.png
[format_png 22]: /images/20230528/8b7a59c267cf4786bf51757b84e89753.png
[format_png 23]: /images/20230528/7ad8167bcbc54e2a9927c115044b2c87.png
[format_png 24]: /images/20230528/7f066067b255498fbc6f7c8c23f82859.png
[format_png 25]: /images/20230528/1dd9062a19964eac937fd8758bdccc48.png
[format_png 26]: /images/20230528/503549399b034c9fbc6c109451f4932d.png
[format_png 27]: /images/20230528/d296824f7d7346109fc8b1791794d579.png
[format_png 28]: /images/20230528/7d43598132904852a9235ee2427751a4.png
[format_png 29]: /images/20230528/232a1dc663c24de1ab55797368952d90.png
[format_png 30]: /images/20230528/1d9c1d1a36fc473c83f760729422db22.png
[format_png 31]: /images/20230528/d2e0d06006ba4ea3943f0ad9956d568e.png
[format_png 32]: /images/20230528/3d5a7e73af4d4e2b896ffbf0e4f80ace.png
[format_png 33]: /images/20230528/23fc85bf5dee4c208244df840a52da23.png
[format_png 34]: /images/20230528/0a250eb19259439b9e1d12ae7992c44f.png
[format_png 35]: /images/20230528/08a7f1227a5a4a44b1e9b2c2af5786f5.png
[format_png 36]: /images/20230528/b4e43abaa2284d9086bfd249e39815c5.png
[format_png 37]: /images/20230528/43ce27af45f24dd9acb7db33f92232c6.png