[Java学习]最⼩⽣成树——Prim算法
⽂章⽬录
最⼩⽣成树
百度百科上对于最⼩⽣成树的定义是这样的：⼀个有 n 个结点的连通图的⽣成树是原图的极⼩连通⼦图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
通俗的解释最⼩⽣成树包括以下两点：(1) 最⼩；(2) 树。
对于树的概念，必须满⾜以下两条性质：
（1）图中没有任何环；
（2）必须连接所有顶点且都是互通的；
故，对于⼀个有N个顶点的树，他有N-1条边。
接下来是最⼩。⼀个图会有若⼲个⽣成树，我们把这些⽣成树边的权值相加称为权值和。不同的⽣成树会有不同的权值和，⽽最⼩⽣成树就是权值和最⼩的那棵树。
⽣成树的⽰意图如下：
求解最⼩⽣成树有两种算法：Prim算法，Kruskal算法，本篇主要介绍⼀下Prim算法。
Prim算法流程
prim 算法采⽤的是⼀种贪⼼的策略。
每次将离连通部分的最近的点和点对应的边加⼊的连通部分，连通部分逐渐扩⼤，最后将整个图连通起来，并且边长之和最⼩。
我们将图中各个节点⽤数字 1 ~ n 编号。
要将所有景点连通起来，并且边长之和最⼩，步骤如下：
(1) ⽤⼀个 st 数组表⽰节点是否已经连通。st[i] 为真，表⽰已经连通，st[i] 为假，表⽰还没有连通。初始时，state 各个元素为假。即所有点还没有连通。
⽤⼀个 dist 数组保存各个点到连通部分的最短距离，dist[i] 表⽰ i 节点到连通部分的最短距离。初始时，dist 数组的各个元素为⽆穷⼤。⽤⼀个 pre 数组保存节点的是和谁连通的。pre[i] = k 表⽰节点 i 和节点 k 之间需要有⼀条边。初始时，pre 的各个元素置为 -1。
(2) 从 1 号节点开始扩充连通的部分，所以 1 号节点与连通部分的最短距离为 0，即disti[1] 置为 0。
(3)遍历 dist 数组，到⼀个还没有连通起来，但是距离连通部分最近的点，假设该节点的编号是 i。i节点就是下⼀个应该加⼊连通部分的节点，st[i] 置为 1。
⽤青⾊点表⽰还没有连通起来的点，红⾊点表⽰连通起来的点。
这⾥青⾊点中距离最⼩的是 dist[1]，因此 st[1] 置为 1。
(4) 遍历所有与 i 相连但没有加⼊到连通部分的点 j，如果 j 距离连通部分的距离⼤于 i j 之间的距离，即 dist[j] > w[i][j]（w[i][j] 为 i j 节点之间的距离），则更新 dist[j] 为 w[i][j]。这时候表⽰，j 到连通部分的最短⽅式是和 i 相连，因此，更新pre[j] = i。
与节点 1 相连的有 2， 3， 4 号节点。1->2 的距离为 100，⼩于 dist[2]，dist[2] 更新为 100，pre[2] 更新为1。1->4 的距离为140，⼩于 dist[4]，dist[4] 更新为 140，pre[2] 更新为1。1->3 的距离为 150，⼩于 dist[3]，dist[3] 更新为 150，pre[3] 更新为1。
(5) 重复 3 4步骤，直到所有节点的状态都被置为 1.
java技术介绍百度百科
这⾥青⾊点中距离最⼩的是 dist[2]，因此 st[2] 置为 1。
与节点 2 相连的有 5， 4号节点。2->5 的距离为 80，⼩于 dist[5]，dist[5] 更新为 80，pre[5] 更新为 2。2->4 的距离为 80，⼩于dist[4]，dist[4] 更新为 80，pre[4] 更新为2。
选dist[4]，更新dist[3]，dist[5]，pre[3]，pre[5]。
选dist[5]，没有可更新的.
选dist[3]，没有可更新的。
(6)此时 dist 数组中保存了各个节点需要修的路长，加起来就是。pre 数组中保存了需要选择的边。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。