邻接表中单链表按顶点编号递增排列！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