《c数据结构chapt8图》由会员分享，可在线阅读，更多相关《c数据结构chapt8图（82页珍藏版）》请在金锄头文库上搜索。
1、第八章第八章 图图 图的定义图的定义 图的存储结构图的存储结构 图的遍历图的遍历 图的应用图的应用8.1 8.1 图的定义和术语图的定义和术语1. 1. 图图有向图（有向图（DigraghDigragh）无向图（无向图（UndigraphUndigraph）8.1 8.1 图的定义和术语图的定义和术语 有向图（有向图（DigraghDigragh）G=G=（V V，AA）其中，其中，V V为顶点的有穷非空集合为顶点的有穷非空集合AA为顶点之间的关系集合为顶点之间的关系集合 G1=（V，A） V=v1, v2, v3, v4 A=, , , 其中表示从x到y的一条弧（arc），A为弧集合，x为弧
2、尾（tail），y为弧头（head)G18.1 8.1 图的定义和术语图的定义和术语 无向图（无向图（UndigraphUndigraph）G=(V,E)G=(V,E)其中，其中，V V同有向图，同有向图，EE为顶点之间的关系集合为顶点之间的关系集合，E E为边集合为边集合G2=（V，A） V=v1, v2, v3, v4, v5 E=(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5)其中，(x, y)表示x与y之间的一条连线，称为边（edge）G2 8.1 8.1 图的定义和术语图的定义和术语设设n n为顶点数，为顶点数，e e为
3、边或弧的条数为边或弧的条数对对无向图无向图有：有：0vj)vivj)viadjvex!=w ) p= p-nextarc; /将移动指针定位到w IF (!p | !p-nextarc) RETURN(0)ELSE RETURN(p-nextarc-adjvex)8.3 8.3 图的遍历图的遍历2. 2. 深度优先搜索递归过程：深度优先搜索递归过程：VOID traver(Graph g, Boolean visitedvtxptr)FOR (V=0; V0)closedgev.lowcost0)printf(closedgek.adjvex,G.vexk); / printf(closedg
4、ek.adjvex,G.vexk); /输出生成树的边输出生成树的边closedgek.lowcost=0; /closedgek.lowcost=0; /顶点顶点k k并入并入U UFOR (j=0 ; j 表示活动表示活动 a ai i优先于活动优先于活动 a aj j ， 称这类有向图为顶点表示活动的网（称这类有向图为顶点表示活动的网（AOVAOV网）。网）。8.5 8.5 拓扑排序拓扑排序( (topological sort)topological sort)AOVAOV网可解决如下两个问题：网可解决如下两个问题： （1 1）判定工程的可行性。显然，有回路，整个工程就无法结束）判定工
5、程的可行性。显然，有回路，整个工程就无法结束 （2 2）确定各项活动在整个工程执行中的先后顺序。）确定各项活动在整个工程执行中的先后顺序。称这种先后顺序为称这种先后顺序为拓扑有序序列拓扑有序序列。如图有如下拓扑有序序列：如图有如下拓扑有序序列： a a1 1 a a2 2 a a3 3a a4 4 a a6 6 a a5 5 a a7 7 a a8 8 a9a9 a a2 2 a a6 6 a a1 1 a a3 3 a a4 4 a a5 5 a a7 7 a a9 9 a a8 8a a1 1a a5 5a a4 4a a6 6a a2 2a a3 3a a8 8a a7 7a a9 98
6、.5 8.5 拓扑排序拓扑排序( (topological sort)topological sort)拓扑排序：满足以下性质的线性序列：拓扑排序：满足以下性质的线性序列：bb在在AOVAOV网中，若顶点网中，若顶点i i 优先于顶点优先于顶点j j ，则在线性序列，则在线性序列 中顶点中顶点i i仍然优先于顶点仍然优先于顶点j j；bb 对于网中原来没有优先关系的顶点与顶点对于网中原来没有优先关系的顶点与顶点 ，在，在 线性序列中也建立一个先后关系，或者顶点线性序列中也建立一个先后关系，或者顶点i i优先于优先于 顶点顶点j j ，或者顶点，或者顶点j j 优先于优先于i i。 二、拓扑排序
7、算法二、拓扑排序算法1. 1.算法步骤算法步骤 (1)(1) 在在AOVAOV网中，选取一个网中，选取一个没有前驱没有前驱的顶点输出；的顶点输出； (2)(2) 删除该顶点和所有以它为弧尾的弧；删除该顶点和所有以它为弧尾的弧； (3)(3) 重复以上两步，直到重复以上两步，直到 AOVAOV网中全部顶点都已输出（得到拓扑有序序列）网中全部顶点都已输出（得到拓扑有序序列） 或者，图中再无没有前驱的顶点（或者，图中再无没有前驱的顶点（AOVAOV网中有环）网中有环）二、拓扑排序算法二、拓扑排序算法如何实现算法中的如何实现算法中的(1)(1)和和(2)(2)？bb对于对于(1)(1)，没有前驱的顶点
8、即入度为，没有前驱的顶点即入度为0 0的顶点；的顶点；bb对于对于(2)(2)，删除以它为弧尾的所有弧，即让该顶点的所，删除以它为弧尾的所有弧，即让该顶点的所 有直接后继的入度减有直接后继的入度减1 1。由此分析知：拓扑排序算法的实现与顶点的入度有密切由此分析知：拓扑排序算法的实现与顶点的入度有密切 关系，因此，在选取存储结构时，应考虑：关系，因此，在选取存储结构时，应考虑： 能容易得到各顶点的入度；能容易得到各顶点的入度； 有利于寻找任一顶点的所有直接后继。有利于寻找任一顶点的所有直接后继。 为此，采用邻接表作为为此，采用邻接表作为AOVAOV网的存储结构，并在头结点网的存储结构，并在头结点
9、 中增加一个存放顶点入度的域（中增加一个存放顶点入度的域（indegreeindegree） V V1 1V V4 4V V6 6V V2 2V V3 3V V5 5V1 V2 V3 V4 V5 V60 2 1 2 3 043252 554V V1 1V V4 4V V6 6V V2 2V V3 3V V5 5V1 V2 V3 V4 V5 V60 2 1 2 3 043252 554步骤 0 1 2 3 4 5 6输出 V6 V1 V3 V2 V4 V5 m 0 1 2 3 4 5 6=n 栈 TOP6 113 442 45入度域02123 01201 2 00100 2 00000 1 00
10、000 1 00000 0 0二、拓扑排序算法二、拓扑排序算法Status toposort(algraph G)/Status toposort(algraph G)/GG采用邻接链表存储。若无回路输出拓扑序列采用邻接链表存储。若无回路输出拓扑序列 finddegree(G,indegree ); / finddegree(G,indegree ); /对各顶点求入度，对各顶点求入度，indegree0.vernum-1indegree0.vernum-1INITstack (s); INITstack (s);FOR (i=0 ; Inextarc )for (p=G.verticesI.
11、firstarc ; p ; p=p-nextarc ) k=p-adjvex ; / k=p-adjvex ; /下面对下面对I I号顶点的每个邻接点的入度号顶点的每个邻接点的入度-1-1if (!(-indegreek) PUSH(top, k); / if (!(-indegreek) PUSH(top, k); /入度减为入度减为0 0的顶点入栈的顶点入栈 /for /for /while /while IF (count 表示活动表示活动a ai i，则有，则有e(i)=ve(j)e(i)=ve(j)vjvkaivr8.6 8.6 关键路径关键路径bb事件事件 v vk k 的最迟发
12、生时间的最迟发生时间 vl(k)vl(k)：是在不推迟整个工期的是在不推迟整个工期的 前提下，该事件最迟必须发生的时间前提下，该事件最迟必须发生的时间bb活动活动a ai i的最迟开始时间的最迟开始时间l(i)l(i)：是该活动的弧头事件的最是该活动的弧头事件的最 迟发生时间与该活动的持续时间之差，迟发生时间与该活动的持续时间之差，即即l(i)=vl(k)- al(i)=vl(k)- ai i 的持续时间的持续时间bb关键活动：关键活动：l(i)=e(i)l(i)=e(i)的活动的活动由此可见：在由此可见：在AOEAOE网中找关键活动问题可转化为求网中找关键活动问题可转化为求 l(i)=e(i
13、)l(i)=e(i)， 而而e(i)=e(i)=ve(j)ve(j)l(i)= l(i)=vl(k) vl(k) - a- ai i 的持续时间的持续时间因此，需先求出事件的最早、最迟发生时间因此，需先求出事件的最早、最迟发生时间v2v3 v1v4v52245 638.6 8.6 关键路径关键路径三、关键路径算法思想三、关键路径算法思想 1. 1. 从从ve(1)=0 ve(1)=0 开始利用下面递推公式，计算出各事件的最开始利用下面递推公式，计算出各事件的最 早发生时间早发生时间 ve(j)=Maxve(i)+dut()ve(j)=Maxve(i)+dut()，j=2, nj=2, n， T
14、T其中：其中：T T是所有以是所有以j j为头的弧集合，为头的弧集合， dut()dut()表示活动的持续时间表示活动的持续时间 前例中，前例中，ve(5)=Maxve(2)+dut()ve(5)=Maxve(2)+dut()，ve(3)+dut()ve(3)+dut()=Max6+1,4+1=7 =Max6+1,4+1=7a1=6a4=1a2=4a5=12. 2. 从从vl(n)=ve(n)vl(n)=ve(n)开始，利用下面递推公式开始，利用下面递推公式 ，计算出各时间的最迟发生时间：，计算出各时间的最迟发生时间： vl(i)=Minvl(j)-dut() vl(i)=Minvl(j)-dut() i=n-1 , 2, 1 , i=n-1 , 2, 1 , SS其中：其中：S S是所有以是所有以i i为尾的弧集合为尾的弧集合8.6 8.6 关键路径关键路径a1=6a4=1a2=4a5=1 前例中，vl(5)=ve(5)=7 vl(2)=vl(5)-1=6vl(3)=vl(5)-1=6 vl
