正文之前
在介绍最小生成树之前，需要先介绍一下生成树的概念：
一棵树 T，如果包含一个连通无向图G中的所有顶点，则称 T 为图G的生成树，一般情况下，图G的生成树不止一棵。
本节将介绍以下内容：
寻找生成树（广度/深度优先搜索）
寻找最小生成树（Prim/Kruskal算法）
正文
寻找生成树(Spanning Trees)
1. 广度优先搜索(Breadth-First-Search)
- 思想：首先处理在同一层次的所有结点，然后再处理下一层次的结点
举例
-
我们先给结点排序：a,b,c,d,e,f,g,h
-
设 a 为根结点，T只包含a
-
给T添加边(a, x)
-
添加(a,b)
-
在结点 b 的基础上执行第3步，添加(b, f), (b, c), (b, e)
-
在结点 f, c, e 的基础上，执行第3步，添加(f, g), (c, d), (e, i)
-
在结点 g, d, i 的基础上，执行第3步，添加(d, h)
-
在结点 h 的基础，没有边可添加，过程结束，生成树已找到
2. 深度优先搜索(Depth-First-Search)
- 思想：尽可能深入地搜索，到达尽头后，沿着每条边回到初始选定的结点，直到发现所有的结点，又称为回溯法(backtracking)
还是以上图为例：
-
我们先给结点排序：a,b,c,d,e,f,g,h
-
设 a 为根结点，T只包含a
-
按照顺序，增加边(a, b), (b, c), (c, d), (d, e), (e, i), (i, h)
-
以结点 h 为基础，不能再增加边，所以开始回溯
-
回溯到结点 c ，增加边(c, g), (g, f)
-
以结点 f 为基础，不能再增加边，又开始回溯
-
回溯到根结点 a ，过程结束，生成树已找到
算法的不同，就会导致寻找到的生成树不同，所以，如果一个图含有生成树，一般情况下不止一棵
寻找最小生成树
在一个图的所有生成树中，权值最小的树被称为最小生成树
打个比方，一个图表示一个省，在省内的各个市之间需要修建公路，图中的每条边的权值表示修建这条公路的费用，如何修建一条连贯各示且费用最低的公路？？
1. Prim算法
- 思想：树的构造从一个结点开始，不断给树加入边，直到形成最小生成树
根据这个图，我们开始演算：
-
我们假设初始结点为 a ，在树 T 中加入结点 a
-
选择与结点 a 相关联的权值最小的边：(a, c)，将其加入 T
-
选择与结点 a 或结点 c 相关联的权值最小的边：(c, b)，将其加入 T ，与结点 a 有关联的边都已被选择，所以不再考虑结点 a
-
选择与结点 c 或结点 b 相关联的权值最小的边：(b, g)，将其加入 T
-
选择与结点 c 或结点 b 或结点 g 相关联的权值最小的边：(g, h)，将其加入 T
-
选择与结点 c 或结点 b 或结点 g 或结点 h 相关联的权值最小的边：(c, d)，将其加入 T ，与结点 b, c 有关联的边都已被选择，所以不再考虑结点 b, c
-
选择与结点 d 或结点 g 或结点 h 相关联的权值最小的边：(d, e)，将其加入 T
-
选择与结点 d 或结点 g 或结点 h 或结点 e 相关联的权值最小的边：(e, f)，将其加入 T
-
所有结点已都在树中，最小生成树已找到，权值为20，过程结束
2. Kruskal算法
- 思想：将图中所有的边按权值升序排列，不断选择权值最小的边加入树中，直至所有结点都已在同一连通分量中
还是以这张图为例：
-
将所有边排序，具体结果就不展示了
-
首先选择边(g, h)，权值为1，加入树 T
-
选择边(g, b)，权值为2，加入 T
-
依次选择边(a, c), (c, b), (e, f), (d, e), (c, d)
-
所有的结点都已在同一连通分量中，最小生成树已找到，权值为20，过程结束
重点
在选择权值为4的边时，如果选择边(a, b)，就会导致形成回路，寻找失败
在选择权值为5的边时，如果选择边(d, f)，就会导致形成回路，寻找失败
这两种方法找到了结构相同的最小生成树，证明此图只有唯一的最小生成树
关于最小生成树的介绍就到此为止了，谢谢！
网友评论