61图的基本概念.PPT

6.4.2 最小生成树算法 Prim算法基本思想： 初始时从V中任取一个顶点（如v1），将其放入U中，使U={v1}，这样集合U与集合V?U就构成图G的一个割。 只要U是V真子集，就不断进行如下的贪心选择：选择一条权值最小的交叉边（vi, vj），其中vi∈U, vj ∈V?U，并把该边（vi, vj）和其不在最小生成树中的顶点vj分别加入T的顶点集U和边集TE中。 这个过程不断重复直到图G中的n个顶点均被加入到最小生成树T中为止。 Prim算法的关键： 如何找到连接U和V-U的最短边。 利用MST性质，可以用下述方法构造候选最短边集： 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。 6.4.2 最小生成树算法——Prim算法 6.4.2 最小生成树算法——Prim算法 在图中，U中顶点U={0，2，5}，V?U中的顶点V?U={1，3，4}，mst[1]存放的是2。因为，U到V?U中的顶点1的边有：（0，1）权值为6，（2，1）权值为5，（5，1）权值为∞，所以，U到V?U中的顶点1的权值最小的边是（2，1）。同样，可求出mst[3]=5，mst[4]=2。它们所对应的lowcost数组分别是：lowcost[1]=（2，1）=5，lowcost[3]=（5，3）=2，lowcost[4]=(2，4)=6。 普里姆算法是在所有U到V-U的边中，找权值是最小的边。而lowcost[i]是U到顶点i∈V-U权值最小的边，所以只要在所有lowcost[i]（i∈V-U）中找出最小的lowcost[K]（V-U），那么（mst[k]，k）就是所有U到V-U的边中，权值是最小的。即生成树包含边（mst[k]，k），将顶点k并入集合U中。 6.4.2 最小生成树算法——Prim算法 6.4.3 最小生成树——Kruskal算法 Kruskal算法基本思想： 设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。 若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路。如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。 25 12 34 19 26 46 38 17 25 A B E D C F A B E D C F 连通分量＝{A}, {B}, {C}, {D}, {E}, {F} 6.4.3 最小生成树——Kruskal算法 6.4.3 最小生成树——Kruskal算法 克鲁斯卡尔算法是按边权值递增次序，构造最小生成树的算法。算法的基本思想是：设带权的连通无向图G=（V，E），有n个顶点。最小生成树的初始状态为有n个顶点但无边的非连通图T=（V，?），图中每一个顶点自成一个连通分量。在图G的边集E中按权值自小至大依次选择边（u，v），若该边依附的顶点u、v分别是当前T的两个连通分量中的顶点，则将该边加入到TE中；若u、v是当前同一个连通分量中的顶点，则舍去此边而选择下一条权值最小的边。依此类推，直到T中所有顶点都在同一连通分量上为止，T便成为G的一棵最小生成树。 6.4.3 最小生成树——Kruskal算法 6.5有向无环图及其应用 AOV网特点： 1.AOV网中的弧表示活动之间存在的某种制约关系。 2.AOV网中不能出现回路 。 6.5.1拓扑排序 拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。 拓扑排序 基本思想： ⑴ 从AOV网中选择一个没有前驱的顶点并且输出； ⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧； ⑶ 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。 AOV网及拓扑序列的产生过程 拓扑排序算法描述如下。 （1）扫描顶点表，将入度为零的顶点入栈。 （2）若栈不为空则转到（3）。若栈求为空，首先，栈顶顶点vj弹出，输出并计数；然后，在邻接表中查vj的直接后继vk，把vk的入度减1，若vk的入度为零则进栈。 （3）判断输出的顶点数，若输出的顶点数小于n，则表示有回路；否则拓扑排序正常结束。 6.5.2 关键路径 有向无环图的另一种图形：AOE网即在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网（A