数据结构与算法－图的应用

生成树的定义

设连通图G=(V,E)，从任一顶点遍历，则图中边分成两部分：E(G) = T(G)+ B(G)，T(G)为遍历通过的边，B(G)为遍历时未通过的边，G’(V，T)为G的子图，称之为G的一棵生成树。

生成树分为 深度优先生成树 和 广度优先生成树。

注意：

1. 图的生成树不是唯一的。

2. 生成树G’是图G的极小连通子图。即V(G)=V(G’)，G’是连通的，且在G的所有连通子图中边数最少（n个顶点，n-1条 边）。

最小生成树

1. 问题的起源

城市架设通讯网，网中n个城市n个顶点，两城市间线路为一条边，每条边都有相应的权重，即架设相应线路的费用。

问题1：n个城市间的通讯网，至少要多少条线路？

答：n个城市间最少的可行的通讯线路就是一棵生成树，至少要n-1条边。

问题2：怎样选择n-1条线路，使总费用最少？

答：合理的取n-1条边，并使边权总和为最少。

2. 最小生成树定义

给定一个带权图，构造带权图的一棵生成树， 使树中所有边的权总和为最小。

3. 最小生成树的构造算法

Prim 算法 和 Kruskal 算法。