河池学院：《数据结构》课程电子教案（PPT教学课件）第8章 图 8.4 生成树和最小生成树

一个有n个顶点的连通图的生成树是一个极小连通子图。 生成树含有图中全部顶点，但只包含构成一棵树的n-1条边。 如果在一棵生成树上添加一条边，必定构成一个环：因为这条边 使得它依附的那两个顶点之间有了第二条路径。 1. 什么是生成树 1/30

连通图：仅需调用遍历过程（DFS或BFS）一次，从图中任一顶点出发， 便可以遍历图中的各个顶点。遍历中搜索边时，若顶点w首次 访问（该边也是首次搜索到），则该边是一条树边，所有树边构成一 棵生成树。 非连通图：需对每个连通分量调用一次遍历过程，所有连通分量对应 的生成树构成整个非连通图的生成森林。 2. 连通图的生成树和非连通图的生成森林 2/30

由深度优先遍历得到的生成树称为深度优先生成树。 由广度优先遍历得到的生成树称为广度优先生成树。 无论哪种生成树，都是由相应遍历中首次搜索的边构成的。 3. 由两种遍历方法产生的生成树 3/30

【例8.14】对于如下的无向图，画出其邻接表存储结构，并在该邻接 表中，以顶点0为根，画出图G的深度优先生成树和广度优先生成树。 0 1 2 3 4 5 6 7 8 9 4/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

邻接表中单链表按顶点编号递增排列！ 0 1 2 3 4 5 6 7 8 9 BFS(0) 0 1 4 BFS树 5 2 3 7 6 8 9 0 1 2 3 4 5 6 7 8 9 6/30

4. 什么是最小生成树 一个带权连通图G（假定每条边上的权值均大于零）可能有多棵生成树. 每棵生成树中所有边上的权值之和可能不同. 其中边上的权值之和最小的生成树称为图的最小生成树。 7/30

1. 普里姆算法过程 普里姆（Prim）算法是一种构造性算法。假设G=(V，E)是一个具有n个 顶点的带权连通图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE 是T的边集，则由G构造从起始点v出发的最小生成树T的步骤如下： （1）初始化U={v}。以v到其他顶点的所有边为候选边。 （2）重复以下步骤n-1次，使得其他n-1个顶点被加入到U中： ① 从候选边中挑选权值最小的边加入TE（所有候选边一定是连接两个顶 点集U和V-U的边），设该边在V-U中的顶点是k，将顶点k加入U中。 ② 考察当前V-U中的所有顶点j，修改候选边：若(k，j)的权值小于原 来和顶点j关联的候选边，则用(k，j)取代后者作为候选边。 8/30

v U 其他 顶点 V-U 移动顶点k，直到U=V 将U和V-U之间的所有边称为割集 移动的顶点k是割集中的最小边（*,k） 9/30

0 1 2 3 4 12 3 54 6 87 0 1 2 3 4 12 3 54 6 87 U V - U 示例 10/30