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

1. 生成树的定义

设连通图G&＃61;(V,E)&＃xff0c;从任一顶点遍历&＃xff0c;则图中边分成两部分&＃xff1a;E(G) &＃61; T(G)&＃43; B(G)&＃xff0c;T(G)为遍历通过的边&＃xff0c;B(G)为遍历时未通过的边&＃xff0c;G’(V&＃xff0c;T)为G的子图&＃xff0c;称之为G的一棵生成树。

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

注意&＃xff1a;

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

2. 生成树G’是图G的极小连通子图。即V(G)&＃61;V(G’)&＃xff0c;G’是连通的&＃xff0c;且在G的所有连通子图中边数最少&＃xff08;n个顶点&＃xff0c;n-1条 边&＃xff09;。

2. 最小生成树

1. 问题的起源

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

问题1&＃xff1a;n个城市间的通讯网&＃xff0c;至少要多少条线路&＃xff1f;

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

问题2&＃xff1a;怎样选择n-1条线路&＃xff0c;使总费用最少&＃xff1f;

答&＃xff1a;合理的取n-1条边&＃xff0c;并使边权总和为最少。

2. 最小生成树定义

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

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

Prim 算法 和 Kruskal 算法。