8.4生成树和最小生成树8.4.1生成树和最小生成树的概念1。什么是生成树一个有n个顶点的连通图的生成树是一个极小连通子图。生成树含有图中全部顶点，但只包含构成一棵树的n-1条边。如果在一棵生成树上添加一条边，必定构成一个环：因为这条边使得它依附的那两个顶点之间有了第二条路径。1/30
一个有n个顶点的连通图的生成树是一个极小连通子图。 生成树含有图中全部顶点，但只包含构成一棵树的n-1条边。 如果在一棵生成树上添加一条边，必定构成一个环：因为这条边 使得它依附的那两个顶点之间有了第二条路径。 1. 什么是生成树 1/30
2：连通图的生成树和非连通图的生成森林连通图：仅需调用遍历过程（DFS或BFS）一次，从图中任一顶点出发便可以遍历图中的各个顶点。遍历中搜索边时，若顶点W首次访问（该边也是首次搜索到），则该边是一条树边，所有树边构成一棵生成树。非连通图：需对每个连通分量调用一次遍历过程，所有连通分量对应的生成树构成整个非连通图的生成森林。2/30
连通图：仅需调用遍历过程（DFS或BFS）一次，从图中任一顶点出发， 便可以遍历图中的各个顶点。遍历中搜索边时，若顶点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
邻接表中单链表按顶点编号递增排列！BFS(0)BFS树6/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
4. 什么是最小生成树 一个带权连通图G（假定每条边上的权值均大于零）可能有多棵生成树. 每棵生成树中所有边上的权值之和可能不同. 其中边上的权值之和最小的生成树称为图的最小生成树。 7/30
普里姆算法8.4.21.普里姆算法过程普里姆（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
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其他顶点移动顶点k，直到U=V将U和V-U之间的所有边称为割集移动的顶点k是割集中的最小边（*,k）9/30
v U 其他 顶点 V-U 移动顶点k，直到U=V 将U和V-U之间的所有边称为割集 移动的顶点k是割集中的最小边（*,k） 9/30
示例.3523V-U58210/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