6-6 图的应用（1）

生成树

生成树：所有顶点均由边连接在一起但不存在回路的图

• 一个图可以有许多棵不同的生成树
• 生成树的特点
  • 生成树的顶点个数与图的顶点个数相同；
  • 生成树是图的极小连通子图，去掉一条边则非连通；
  • 一个有n个顶点的连通图的生成树有n-1条边；
  • 在生成树中再加一条边必然形成回路
  • 生成树中任意两个顶点间的路径是唯一的

• 含n个顶点n-1条边的图不一定是生成树

深度优先生成树 vs. 广度优先生成树

6-6 图的应用（2）

最小生成树

最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树

6-6 图的应用（3）

构造最小生成树（Minimum Spanning Tree）

构造最小生成树的算法很多，其中多数算法都利用了MST的性质