数据结构8图8+2.ppt

1 第七章图 图的定义 图的存储表示 图的遍历 图的应用 1最小生成树 2拓扑排序 3连通图关键路径 4两点之间的最短路径问题 2 图是由一个顶点集V和一个弧集R构成的数据结构 Graph V R 其中 VR v w V且P v w 表示从v到w的一条弧 并称v为弧尾 w为弧头 谓词P v w 定义了弧的意义或信息 7 1图的定义和术语 3 由于 弧 是有方向的 因此称由顶点集和弧集构成的图为有向图 例如 G V VR 其中V A B C D E VR 4 V V1 V2 V3 V4 V5 V6 V7 E 有些问题需要用有向图来表示 如各门课程之间存在一种 先后次序 关系 若以顶点表示课程 则课程间的次序关系可以顶点间的 弧 来表示 5 若 VR必有 VR 则称顶点v和顶点w之间存在一条边 用 v w 表示 由顶点集和边集构成的图称作无向图 例如 G2 V2 VR2 V2 A B C D E F VR2 A B A E B E C D D F B F C F 6 B 设图G V VR 和图G V VR 且V V VR VR 则称G 为G的子图 15 9 7 21 11 3 2 弧或边带权的图分别称作有向网或无向网 7 假设图中有n个顶点 e条边 则 含有e n n 1 2条边的无向图称作完全图 含有e n n 1 条弧的有向图称作有向完全图 若边或弧的个数e nlogn 则称作稀疏图 否则称作稠密图 8 假若顶点v和顶点w之间存在一条边 则称顶点v和w互为邻接点 例如 D B 3 D A 2 边 v w 和顶点v和w相关联 顶点v的度 与顶点v相关联的边的数目 右侧图中 9 顶点的出度 以顶点v为弧尾的弧的数目 对有向图来说 顶点的入度 以顶点v为弧头的弧的数目 顶点的度 D 出度 OD 入度 ID 例如 ID B 2 OD B 1 D B 3 由于弧有方向性 则有入度和出度之分 10 设图G V VR 中的一个顶点序列 u vi0 vi1 vim w 中 vi j 1 vi j VR1 j m 则称从顶点u到顶点w之间存在一条路径 路径上边的数目称作路径长度 如 从A到D长度为3的路径 A B C D 简单路径 指序列中顶点不重复出现的路径 简单回路 指序列中第一个顶点和最后一个顶点相同的路径 11 若图G中任意两个顶点之间都有路径相通 称此图为连通图 若无向图为非连通图 则图中各个极大的连通子图称作此图的连通分量 12 若任意两个顶点之间都存在一条有向路径 则称此有向图为强连通图 对有向图 否则 其各个强连通子图称作它的强连通分量 A E 13 假设一个连通图有n个顶点和e条边 其中n 1条边和n个顶点构成一个极小连通子图 称该极小连通子图为此连通图的生成树 对非连通图 则称由各个连通分量的生成树的集合为此非连通图的生成森林 14 结构的建立和销毁 插入或删除顶点 对邻接点的操作 图的遍历 插入和删除弧 图的基本操作 15 CreatGraph 按定义 V VR 构造图 DestroyGraph G 销毁图 结构的建立和销毁 对邻接点的操作 FirstAdjVex G v 返回v的 第一个邻接点 若该顶点在G中没有邻接点 则返回 空 NextAdjVex G v w 返回v的 相对于w的 下一个邻接点 若w是v的最后一个邻接点 则返回 空 16 插入或删除顶点 InsertVex 在图G中增添新顶点v DeleteVex 删除G中顶点v及其相关的弧 插入和删除弧 InsertArc 在G中插入弧 若G是无向图 插入边 w v DeleteArc 在G中删除弧 若G是无向图 则删除边 w v 17 图的遍历 DFSTraverse G v 从顶点v开始按深度优先的原则对图G中的每 个顶点访问且仅访问遍历 BFSTraverse G v 从顶点v开始起按广度优先的原则对图G中的每 个顶点访问且仅访问一遍 18 一 图的数组 邻接矩阵 存储表示 二 图的邻接表存储表示 三 有向图的十字链表存储表示 四 无向图的邻接多重表存储表示 7 2图的存储结构 五 边集数组表示 19 用来表示图中顶点间相邻关系的矩阵 网的邻接矩阵如何表示 7 2 1邻接矩阵表示法 邻接矩阵的定义 20 有向图的邻接矩阵 有向网的邻接矩阵 21 1 当图的各顶点的序号确定后 其邻接矩阵是唯一确定的 2 无向图和无向网的邻接矩阵是一个对称矩阵 3 无向图的邻接矩阵中第i行 或第i列 的非零元个数为第i个顶点的度 邻接矩阵的性质 4 有向图的邻接矩阵中第i行非零元个数为第i个顶点的出度 第i列非零元个数为第i个顶点的入度 5 无向图的边数等于矩阵中非零元个数的一半 有向图的弧数等于矩阵中非零元的个数 或 22 图的邻接矩阵的C语言描述 defineVNUM 图中顶点的最大数目typedefstruct VertexTypevexs VNUM 定义顶点intarcs VNUM VNUM 定义边 弧 intvexnum arcnum 顶点数 弧数 Graph 定义图 网的邻接矩阵的C语言描述 defineVNUM 图中顶点的最大数目typedefstruct VertexTypevexs VNUM 定义顶点WeightTypearcs VNUM VNUM intvexnum arcnum 定义边的权值 NetGraph 定义网 顶点的信息 用一维数组来存储 边的信息 用邻接矩阵来存储 图的邻接矩阵存储方式 23 例 已知一个无向图 建立其存储结构 voidcrt gragh Gragh ga scanf ga vexnum ga arcnum 顶点数和边数for i 0 i ga vexnum i scanf ga vexs i for i 0 i ga vexnum i for j 0 j ga vexnum j ga arcs i j 0 for k 0 k arcnum k scanf i j 读入一条边ga arcs i 1 j 1 1 ga arcs j 1 i 1 1 crt gragh 24 已知一个有向网 建立其存储结构 voidcrt net NetGraph ga scanf ga vexnum ga arcnum 顶点数和弧数for i 0 i ga vexnum i scanf ga vexs i for i 0 i ga vexnum i for j 0 j ga vexnum j ga arcs i j MAXINT for k 0 k ga arcnum k scanf i j w 读入一条弧和弧上的权值ga arcs i 1 j 1 w crt net 25 邻接矩阵的特点 1 邻接矩阵可以采用压缩存储方法无向图和无向网的邻接矩阵为对称矩阵 对于边 弧 个数较少的稀疏图 其邻接矩阵也稀疏 用行主序存储矩阵时存储空间利用率低 2 操作特点其存储特点是一种顺序存储结构 较为适合操作有 计算顶点的度 求一个顶点的所有邻接点 插入或删除一条边 弧 等 不太适合的操作有 顶点的插入和删除 图的遍历等 26 方法 对图中每个顶点建立一个有邻接关系的顶点单链表 顶点邻接表 2 用一个数组存各邻接表的头结点 顶点结点 7 2 2邻接表 对于无向图 第i个链表是与Vi相邻接的所有邻接点构成的单链表 对于有向图 第i个链表是以Vi为弧尾的所有弧头结点构成的单链表 27 typedefstructArcNode intadjvex 该弧所指向的顶点的位置structArcNode nextarc 指向下一条弧的指针 InfoTypeinfo 该弧相关信息 ArcNode ArcPointer 邻接表的组织 typedefstruct VertexTypevexdata 顶点信息ArcPointerfirstarc 出边头指针 指向第一条出边 VexNode typedefstruct VexNodeadjlist Vnum 邻接表intvexnum arcnum 有向图的当前顶点数和弧数 AdjGraph 28 无向图的邻接表 012345 ABCDEF 无向网的邻接表 已知图的邻接表 如何求无向图中的顶点vi的度 无向图中边的个数 29 有向图的邻接表 有向图的逆邻接表 如何求有向图中弧的个数 如何求有向图中顶点vi的出度和入度 30 有向图的邻接表 如何生成有向图的邻接表结构 读入图的信息 顶点信息 ABCDE弧 或边 的信息 例如 0 10 41 22 33 03 14 2 31 建立有向图的邻接表的算法 voidbuild adjlist AdjGraph gb scanf gb vexnum gb arcnum 顶点个数和弧数for i 0 i gb vexnum i scanf gb adjlist i verdata gb adjlist i firstarc NULL for k 0 k gb arcnum k scanf i j 读入一对顶点序号p ArcPointer malloc sizeof ArcNode p adjver j 生成结点p nextarc gb adjlist i firstarc gb adjlist i firstarc p build adjlist 问 如何建立无向图的邻接表 32 1 图的邻接表的表示不是唯一的 它与邻接点的读入顺序有关 2 无向图邻接表中第i个单链表中结点个数为第i个顶点的度 3 有向图邻接表中第i个单链表中结点个数为第i个顶点的出度 其逆邻接表中第i个单链表中结点个数为第i个顶点的入度 邻接表的性质 4 无向图的边数为邻接表中结点个数的一半 有向图的弧数为邻接表中结点个数 33 邻接表的特点 存储特点 是一种顺序 链式的存储结构 当图中顶点个数较多 而边比较少时 可节省大量的空间 较为适合操作有 计算顶点Vi的出度 求一个顶点的所有邻接点 插入或删除一条边 弧 求顶点的一个邻接点的下一个邻接点等 不太适合的操作有 顶点的插入和删除 顶点的入度等 34 链表结点 是有向图的邻接表和逆邻接表结合起来得到的一种链表 7 2 3十字链表 表头结点 35 typedefstructVexNode 定义顶点 头 结点VertexTypedata ArcNode firstin firstout VexNode typedefstructArcBox 定义弧结点inttailvex headvex structArcBox hlink tlink InfoTypeinfo ArcNode 十字链表的组织 36 defineVnum20typedefstruct VexNodeortholist Vnum 顶点 表头 结点数组intvexnum arcnum 有向图的当前顶点数和弧数 OlGraph 有向图的结构表示 十字链表 37 012 读入弧 0 1 0 2 2 0 2 1 38 边结点 ilink 指示下一条依附于顶点ivex的边 jlink 指示下一条依附于顶点jvex的边 data 存储和该顶点相关的信息 firstedge 指示第一条依附于该顶点的边 顶点结点 7 2 4 无向图的 邻接多重表 39 例 对于无向图 读入顺序如下 边结点 40 typedefstructENode intivex jvex 顶点序号structenode ilink jlink ENode typedefstructVNode DataTypedata 顶点信息ENode firstedge 指向第一条依附于该顶点的边结点 VNode 定义头结点typedefstruct VNodeadjmulist Vnum intvexnum edgenum 图的当前顶点数和边数 AMLGrahp 41 方法 用一个一维数组存储顶点信息 用一个一维数组存图中所有的边 数组规模 图边数 每个数组元素存一条边的起点 终点 权值 次序任意无向图 边起点可以任意选定 无权图 省去权值存储 7 2 5边集数组 边集数组 适合 对边依次处理的运算 42 7 3图的遍历 遍历 从某顶点出发 按一定搜索方法 不重复访问所有顶点 问题 可能存在多条路径都能到达同一顶点 即要解决顶点的重复访问 解决办法 对已访问过的顶点做标记 设辅助数组 intvisited n 来记录每个顶点是否被访问过 访问过为1 否则为0 43 7 3 1连通图的深度优先搜索 Depth FirstSearch 访问顶点的次序 V3 V2 V4 V9 V1 V6 V5 V8 V7 深度优先遍历 访问出发点V0 任选一个出发点的一个没被访问过的邻接点 以该点出发深度优先遍历 重复 直到V0没有邻接点没被访问 44 连通图的深度优先遍历的逻辑算法 voiddf traver graghg intv 从v号顶点出发 深度优先遍历连通图gprintf v visited v 1 w FirstAdjVex g v w为v的第一个邻接点编号while w存在 if visited w 0 df traver g w w NextAdjVex g v w 找v的下一个邻接点 dfs 45 typedefstructArcNode intadjvex 该弧所指向的顶点的位置structArcNode nextarc 指向下一条弧的指针 ArcNode ArcPointer 邻接表的组织 typedefstruct VertexTypevexdata 顶点信息ArcPointerfirstarc 出边头指针 指向第一条出边 VexNode typedefstruct VexNodeadjlist Vnum 邻接表intvexnum arcnum 有向图的当前顶点数和弧数 AdjGraph 46 voiddf traver AdjGraphg intv g的存储结构为邻接表 v为出发点编号 标志数组已初始化为0printf g adjlist v vexdata 访问出发点visited v 1 做标志p g adjlist v firstarc 找邻接点while p NULL w p adjvex if visited w 0 df traver g w 递归调用p p nextarc 找下一个邻接点 dfs 47 从图中的某个顶点V0出发 访问此顶点之后依次访问V0的所有未被访问过的邻接点 之后按这些顶点被访问的先后次序依次访问它们的邻接点 7 3 2连通图的广度优先搜索 Breadth FirstSearch 一层 二层 三层 访问顶点的次序 V3 V2 V1 V6 V4 V5 V9 V8 V7 48 显然 先被访问的顶点 其邻接点也先被访问 实现时需要设置一个队列 用于记住访问顶点的次序 算法 1 访问初始顶点 并将其顶点号入队 2 队列不空 则队头顶点号出队 依次访问它的每一个未访问的邻接点 并将其顶点号入队 3 重复2 直到队列空 遍历过程结束 49 邻接表结构下连通图的广义优先遍历算法 voidbf traver AdjGraphg intv0 队列Q存放已访问过的顶点编号 v0为出发点编号InitQueue Q printf g adjlist v0 vexdata visited v0 1 AddQueue Q v0 while Qempty Q v DelQueue Q p g adjlist v firstarc while p NULL w p adjvex 取邻接点编号if visited w 0 printf g adjlist w vexdata visited w 1 AddQueue Q w p p nextarc bfs 50 voidtraver graghg for v 0 v n v visited v 0 for v 0 v n v if visited v 0 df traver g v 或bf travers g v 从图中的某个顶点V0出发深度 广度 优先遍历 之后另选图中一个未曾被访问的顶点作起始点 重复上述过程 直至图中所有顶点都被访问到为止 7 3 3非连通图的深度 广度 优先遍历 51 7 4图的连通性问题 7 4 1无向图的连通分量和生成树 假设要在n个城市之间建立通讯联络网 则连通n个城市只需要修建n 1条线路 如何在最节省经费的前提下建立这个通讯网 问题 52 图G中的边集合E G 分成两个部分 T G 与G中所有顶点构成G的极小连通子图 即是G的一棵生成树 深度优先生成树 B G 剩余的边集 T G 遍历过程中经过的边集 生成树 广度优先生成树 53 已知一个带权图 求其生成树 使得树中所有边上的权值之和最小 最常用的算法 普里姆 prim 算法卡鲁斯卡尔 kruskal 算法 7 4 2最小生成树 54 1 普里姆 prim 算法设G V E 是连通图 最小生成树T的顶点集合为U 边的集合是TE 首先 U u0 u0 V TE 重复执行下述操作 在所有u U v V U的边 u v E中找一条代价最小的边 ui v0 并入集合TE 同时v0并入U 直到U V为止 55 例如 a e d c b g f 14 8 5 3 16 21 所得生成树权值和 14 8 3 5 16 21 67 56 带权图 网 用邻接矩阵表示 struct VertexTypeadjvex U集中的顶点WeightTypelowcost 边的权值 closedge VNUM 最小生成树用一个结构数组 closedge 表示 数组下标表示图中的顶点序号 对当前V U集中的每个顶点 记录和顶点集U中顶点相连接的代价最小的边 typedefstruct VertexTypevexs VNUM WeightTypearcs VNUM VNUM intvexnum arcnum NetGraph 57 abcdefg a e d c b a a a 19 14 18 14 e 12 e e 8 16 8 d 3 d d 7 21 3 c 5 5 16 21 g f 19 14 1819 5712 5 3 73 821 1412 8 16 21 2718 1627 G arcs i j 58 voidMiniSpanTree P NetGraphG VertexTypeu 带权的连通图G的存储结构为邻接矩阵NetGraph 用普里姆算法从顶点u出发构造网G的最小生成树k LocateVex G u 确定起点u在图G中的位置for j 0 j G vexnum j 辅助数组初始化if j k closedge j adjvex u closedge j lowcost G arcs k j closedge k lowcost 0 初始 U u for i 0 i G vexnum i 59 k minimum closedge 求出加入生成树的下一个顶点 k printf closedge k adjvex G vexs k closedge k lowcost 输出生成树上一条边closedge k lowcost 0 第k顶点并入U集for j 0 j G vexnum j 修改其它顶点的最小边if G arcs k j closedge j lowcost closedge j adjvex G vexs k closedge j lowcost G arcs k j MiniSpanTree P 60 设G V E 是连通图 将边从小到大排序 将n个顶点分成n棵树 选最小的一条边 u v 满足u v不在同一连通集 重复 选够n 1条边停止 0 2 1 1 2 5 3 5 2 2 3 5 1 4 3 0 1 6 2 5 4 2 4 6 0 3 5 4 5 6 X 二 卡鲁斯卡尔 kruskal 算法 61 普里姆算法 克鲁斯卡尔算法 时间复杂度 O n2 O eloge 稠密图 稀疏图 算法名 适应范围 比较两种算法 62 7 5有向无环图及其应用 有向无环图 directedacyclinegraph 以有向图表示一个工程的施工图或程序的数据流图 则图中不允许出现回路 63 7 5 1拓扑排序 一 拓扑排序问题的提出 在现实世界中 一项大的工程通常有若干个子工程构成 这些子工程和主工程的关系可以用有向图来描述 子工程称为活动 Activity 活动之间经常存在先后的次序关系 64 在一个有向图中如果用顶点表示活动 用弧表示活动间优先关系 该图称为用顶点表示活动的网 ActivityOnVertexNetwork 简称AOV 网 i是j的前驱 j是i的后继 i是k的直接前驱 k是i的直接后继 二 AOV 网 65 三 拓扑序列的定义 设图G是一个具有n个顶点的有向图 包含图G的所有n个顶点的一个序列 Vi1 Vi2 Vin 当满足下面条件时该序列称为G的一个拓扑序列 当在图G中 从顶点Vi到顶点Vj有一条路径时 在序列中Vi必须排在Vj的前面 构造拓扑序列的过程称为拓扑排序 66 例如 在如下的AOV 网中 序列 v1v3v2v4v5v6v7是一个拓扑序列 序列 v2v1v3v5v4v7v6也是一个拓扑序列 67 例如 对于下列有向图 可求得拓扑有序序列 ABCD或ACBD 对于下列有向图 不能求得它的拓扑有序序列 存在一个回路 四 拓扑序列的特点 1 一个有向图的拓扑序列一般不唯一 2 有向无环图一定存在拓扑序列 68 五 拓扑排序的算法描述 如果顶点没有全部输出 且当前图中不存在无前驱的顶点 则说明有向图中存在环 1 在有向图中选一个没有前驱的顶点且输出 2 从图中删除该顶点以及以该顶点为弧尾的所有弧 重复上述两步 直至全部顶点均已输出 69 例 a 输出V1 b 输出V6 c 输出V4 d 输出V3 e 输出V2或V5 拓扑序列 V1V6V4V3V2V5V1V6V4V3V5V2V6 70 邻接表存储结构中实现拓扑排序的算法可用加了入度域 id 的头结点的邻接表来存储有向图 弧的读入顺序如下 0 1 0 2 0 3 2 1 2 4 3 2 3 4 5 3 5 4 用一个顺序栈存放入度为0的顶点序号 71 1 逻辑算法 InitStack s 将所有入度为零的顶点的栈 m 0 m记已输出顶点的个数while Empty s v Pop s printf v m m 1 w FirstAdjvex g v while w存在 入度 w 入度 w 1 if 入度 w 0 push s w w NextAdjvex g v w if m n returnERROR 该图有回路elsereturnOK 72 2 邻接表结构下的算法 typedefstructarcnode intadjvex 邻接点位置structarcnode nextarc 下一个弧结点指针 ArcNode ArcPointer typedefstruct DataTypevexdata 顶点类型intid 入度ArcPointerfirstarc 头指针 VexNode typedefstruct VexNodeadjlist Vnum 邻接表intvexnum arcnum 有向图的当前顶点数和弧数 AdjGraph 73 statustop sort AdjGraphg InitStack s m 0 初始化顺序栈sfor i 0 i g vexnum i if g adjlist i id 0 Push s i while Empty s v Pop s printf g adjlist v vexdata m m 1 p g adjlist v firstarc while p NULL w p adjvex g adjlist w id if g adjlist w id 0 Push s w p p nextarc if m n returnERROR elsereturnOK top sort 74 先输出v5 栈s 50 按topsort算法得到的拓扑序列为 V5 V0 V3 V2 V1 V4 1 2 0 1 1 1 0 0 0 3 2 4 1 75 AOE 网 activityonedge 在对工程进度进行管理时 往往用顶点表示事件 弧表示活动 弧上的权表示活动持续的时间 这种网称为AOE网 7 5 2关键路径 76 1 完成整项工程至少要花多少时间 整个工程完成的时间为 从有向图的源点到汇点的最长路径 源点 汇点 6 1 7 4 2 哪些活动是影响工程进度的关键 关键路径 路径长度最长的路径 关键活动 关键路径上的所有活动 77 事件Vi的最早发生时间 从源点到Vi的最长路径长度 l i e i 完成活动ai的余量 定义 当e i l i 时 活动ai为关键活动 定义 e i 活动ai的最早 early 开始时间 l i 活动ai的最迟 late 开始时间 也是以Vi为尾的弧所表示的活动的最早开始时间 78 可知Ve j 是以Vj为弧尾的活动ai的最早开始时间即 Ve j e i weight 活动ai的持续时间 事件j 顶点 的最早发生时间Ve j Ve j 从源点到顶点j的最长路径长度 事件k 顶点 的最迟发生时间Vl k Vl k 从顶点k到汇点的最短路径长度 定义 79 假设第i条弧为 活动ai 弧 的最早开始时间e i e i Ve j 活动ai 弧 的最迟开始时间l i l i Vl k weight 事件发生时间的计算公式 已知 Ve 源点 0Vl 汇点 Ve 汇点 80 求Ve j 和Vl j 需分两步进行 1 从Ve 1 0开始向前递推 Ve j max Ve i weight i P j 其中 P j 是以j为弧头的弧尾顶点的集合计算时按拓扑顺序进行 2 从Vl n Ve n 起向后递推 Vl j min Vl k weight k S j S j 是以j为弧尾的弧头顶点的集合计算时按逆拓扑顺序进行 81 求关键路径的算法 1 输入顶点和弧信息 建立其存储结构 2 从源点v1出发 令Ve 1 0 按拓扑有序求各顶点的最早发生时间Ve i 2 i n 3 从汇点Vn出发 令Vl n Ve n 按逆拓扑有序求各顶点的最迟发生时间Vl i 1 i n 1 4 根据各顶点的Ve和Vl值 及公式e i Ve j l i Vl k weight 求每条弧ai的最早开始时间e i 和最迟开始时间l i 82 V1V2V3V4V5V6V7V8V9 064577161418 0668710161418 a1a2a3a4a5a6a7a8a9a10a11 83 算法描述输入顶点和弧信息 建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Ve i 将得到的拓扑序列进栈按逆拓扑序列求顶点的Vl i 计算每条弧的e i 和l i 找出e i l i 的关键活动 84 计算各顶点的Ve值在拓扑排序的过程中进行 需对拓扑排序的算法作如下修改 a 在拓扑排序之前设初值 令ve i 0 1 i n b 在拓扑排序的算法中增加一个计算Vj的直接后继Vk的最早发生时间的操作 若ve j weight ve k 则ve j weight ve k c 为计算各顶点的vl值 需记下逆拓扑有序序列可在拓扑排序算法中 增设一个栈S1记录拓扑有序序列 两个数组 TimeTypeve n vl n 85 000000000 6 4 5 7 7 15 14 17 181818181818181818 16 14 7 6 6 10 8 3 拓扑序列为 a b c e g d f h k 18 2 0 86 voidcritical path AdjGraphg 为求ve i 用栈s1存放入度为0的顶点序号 为求vl i 用栈s2存放拓扑序列的顶点序号 ve 0 g vexnum 1 0 initstack s1 initstack s2 for i 0 i g vexnum i if g adjlist i id 0 push s1 i 入度为0的顶点序号入栈while empty s1 j pop s1 取拓扑序列顶点序号push s2 j 存拓扑序列顶点序号p g adjlist j link while p NULL k p adjvex g adjlist k id if g adjlist k id 0 push s1 k 87 if ve j p weight ve k ve k ve j p weight p p nextarc end while p NULL end while emptp s1 求Ve j 完成 vl 0 g vexnum 1 ve g vexnum 1 初始化l i vl n while empty s2 按逆拓扑序列求各顶点的vl值 j pop s2 p g adjlist j link while p NULL k p adjvex if vl k p weight vl j vl j vl k p weight p p nextarc end while p NULL end while empty s2 求Vl j 完成 88 for j 0 j g vexnum j 已知ve i vl i 求e和lp g adjlist j link while p NULL k p adjvex e ve j l vl k p weight if e l tag elsetag 标志关键活动printf j k p weight e l tag p p nextarc end while end for critical path 89 给定有向图G V E G中E上的权值为W e 设源点的编号为v0 G的存储结构为邻接矩阵 WeightTypenet N N 7 6最短路径 7 6 1从某个源点到其余各顶点的最短路径 存储结构 90 Dijkstra算法 按路径长度递增的次序产生最短路径 如源点到其它每一个顶点都有一条最短路径 v0 v1 v0 v2 v0 vn 在上面的路径中 先求最短的 再求次短的 首先将网中的所有顶点分成两个集合S和T S 凡以v0为源点 已经确定了最短路径的终点并入集合S S的初始状态只包含v0 T 尚未确定最短路径的顶点的集合 其初始状态包含除源点外的所有顶点 91 引进两个辅助数组来记源点 设其编号为v0 到其它顶点的最短路径长度和路径集合 dist i 表示v0到顶点vi的最短路径的长度 path i 表示以上路径中所经过的顶点集合其初始状态为 dist i net v0 i path i v0 i 当 E 否则初始时S v0 以后不断地修改S和dist i 设第一条最短路径为 v0 vj 则dist j min dist i vi T 此时S v0 j 92 假设下一条次短路径的终点是vk 则这条路径或者是 v0 vk 或者是 v0 vj vk 所以有必要修改v0号顶点到除j号顶点以外其它顶点的距离 即修改dist i i T dist i min net v0 i dist j net j i j S i T 重复执行下述操作 直到选够n 1条路径 1 设下一条所选路径的终点为vk 则 dist k min dist i i T 将k加入到S中 2 修改dist i i T dist i min dist i dist k net k i k S i T 93 v1v2v3v4v5入选S的点dist i 10 30100path i v0 v2 v0 v4 v0 v5 从v0出发 10 v0 v2 dist i 6030100path i v0 v2 v3 dist i 50 90path i v0 v4 v3 v0 v4 v5 dist i 60path i v0 v4 v3 v5 30 v0 v4 50 v0 v4 v3 60 v0 v4 v3 v5 v2 v4 v3 v5 94 存储结构 Adjmatrixnet n n 存储有向网的邻接矩阵 WeightTypedist n dist i 存储v0到vi的路径长度 intinset n 若vi在顶点集合S中 则inset i 1 否则inset i 0 初始时 inset v0 1 其它为0 intpath n n 二维数组 path i 是一维数组 存储源点v0到各顶点vi的最短路径 若path i k 1 表示vk在该路径中 95 voidshortpath Adjmatrixnet intv0 WeightType dist n int path n n for i 0 i n i dist inset path初始化 dist i net v0 i inset i 0 所有顶点都不在S中path i 0 n 1 0 所有path i 为空路径if dist i MAXINT path i v0 1 path i i 1 如果dist i 让path i v0 vi 初始化完成inset v0 1 初始化集合S v0 96 for k 0 k n k 构造至多n 1条路径 min MAXINT j v0 初始化一个最短路径长for i 0 i n i 找入选点及min值if inset i 0 dist i min j i min dist j min min dist i i T if j v0 inset j 1 S S j for i 0 i n i 修改