8.4生成树和最小生成树8.4.1生成树和最小生成树的概念1。什么是生成树一个有n个顶点的连通图的生成树是一个极小连通子图。生成树含有图中全部顶点，但只包含构成一棵树的n-1条边。如果在一棵生成树上添加一条边，必定构成一个环：因为这条边使得它依附的那两个顶点之间有了第二条路径。1/30
一个有n个顶点的连通图的生成树是一个极小连通子图。 生成树含有图中全部顶点，但只包含构成一棵树的n-1条边。 如果在一棵生成树上添加一条边，必定构成一个环：因为这条边 使得它依附的那两个顶点之间有了第二条路径。 1. 什么是生成树 1/30
2：连通图的生成树和非连通图的生成森林连通图：仅需调用遍历过程（DFS或BFS）一次，从图中任一顶点出发便可以遍历图中的各个顶点。遍历中搜索边<V，W>时，若顶点W首次访问（该边也是首次搜索到），则该边是一条树边，所有树边构成一棵生成树。非连通图：需对每个连通分量调用一次遍历过程，所有连通分量对应的生成树构成整个非连通图的生成森林。2/30
连通图：仅需调用遍历过程（DFS或BFS）一次，从图中任一顶点出发， 便可以遍历图中的各个顶点。遍历中搜索边<v，w>时，若顶点w首次 访问（该边也是首次搜索到），则该边是一条树边，所有树边构成一 棵生成树。 非连通图：需对每个连通分量调用一次遍历过程，所有连通分量对应 的生成树构成整个非连通图的生成森林。 2. 连通图的生成树和非连通图的生成森林 2/30
3：由两种遍历方法产生的生成树由深度优先遍历得到的生成树称为深度优先生成树。由广度优先遍历得到的生成树称为广度优先生成树。无论哪种生成树，都是由相应遍历中首次搜索的边构成的。3/30
由深度优先遍历得到的生成树称为深度优先生成树。 由广度优先遍历得到的生成树称为广度优先生成树。 无论哪种生成树，都是由相应遍历中首次搜索的边构成的。 3. 由两种遍历方法产生的生成树 3/30
【例8.14】对于如下的无向图，画出其邻接表存储结构，并在该邻接表中，以顶点0为根，画出图G的深度优先生成树和广度优先生成树。4/30
【例8.14】对于如下的无向图，画出其邻接表存储结构，并在该邻接 表中，以顶点0为根，画出图G的深度优先生成树和广度优先生成树。 0 1 2 3 4 5 6 7 8 9 4/30
邻接表中单链表按顶点编号递增排列！DFS(0)0>1DFS树23768C5/30
邻接表中单链表按顶点编号递增排列！ 0 1 2 3 4 5 6 7 8 9 0 1 4 5 2 3 7 6 8 9 DFS(0) 0 1 2 3 4 5 6 7 8 9 DFS树 5/30