数据结构 第七章 图 7.1—7.2.ppt

第7章图 线性表中 数据元素之间仅有线性关系 每个数据元素只有一个直接前驱和一个直接后继 在树形结构中 数据元素之间有着层次关系 每一层上的数据元素可能和下一层中多个元素相关 只能和上一层中一个元素相关 在图形结构中 结点之间的关系是任意的 图中任意两个数据元素之间都可能相关 7 1图的定义和术语 7 2图的存储结构 7 3图的遍历 7 4图的连通性问题 7 5有向无环图及其应用 7 6最短路径 图是由一个顶点集V vertex 和一个弧集 边集 R arc 构成的数据结构 Graph V R 其中数据关系R R VR VR v w V且P v w 表示从v到w的一条弧 谓词P v w 定义了弧的意义或信息 图的定义 7 1图的定义和术语 顶点 图中的数据元素 若 VR 则表示从v到w的一条弧 v为弧尾 初始点 w为弧头 终端点 由于 弧 是有方向的 因此称由顶点集和弧集构成的图为有向图 例如 G1 V1 VR1 其中V1 A B C D E VR1 若 VR必有 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 名词和术语 权 网 子图 完全图 有向完全图 稀疏图 稠密图 邻接点 依附 相关联 度 入度 出度 路径 回路 环 简单路径 简单回路 简单环 连通 连通图 连通分量 强连通图 强连通分量 生成树 生成森林 假设图中有n个顶点 e条边 则 含有e n n 1 2条边的无向图称作完全图 含有e n n 1 条弧的有向图称作有向完全图 图中最大边数是多少 图中最大弧数是多少 有很少条边或弧 e nlogn 的图称为稀疏图 否则称作稠密图 权 与图的边或弧相关的数 网 带权的图 B 有两个图G V E 和图G V E 且V V E E 则称G 为G的子图 A B E C F 例如 TD B TD A 边 v v 依附于顶点v和v 边 v v 和顶点v和v 相关联 顶点v的度是和顶点v相关联的边的数目 对于无向图G V E 如果边 v v E 则称v和v 互为邻接点 即v和v 相邻接 3 2 顶点的出度 OutDegree 以顶点v为尾的弧的数目 顶点的入度 InDegree 以顶点v为头的弧的数目 ID B 例如 OD B TD B 对于有向图G V A 如果弧 A 则称顶点v邻接到顶点v 顶点v 邻接自顶点v 顶点的度 TD 出度 OD 入度 ID 1 2 3 无向图G V E 中从顶点v到顶点v 的路径是一个顶点序列 v vi 0 vi 1 vi m v 其中 vi j 1 vi j E 1 j m 如果G是有向图 则路径也是有向的 顶点序列应满足 E 1 j m 路径长度是路径上边的数目 A B E C F 简单路径 序列中顶点不重复出现的路径 简单回路 简单环 除了第一个顶点和最后一个顶点之外 其余顶点不重复出现的回路 回路 环 第一个顶点和最后一个顶点相同的路径 ABCFABCFAECFA 若图G中任意两个顶点vi vj V vi和vj都是连通的 则称此图为连通图 B A C D F E 在无向图G中 如果从顶点v到顶点v 有路径 则称v和v 是连通的 无向图中的极大连通子图是连通分量 在有向图中 对于每一对vi vj V vi vj 从vi到vj和从vj到vi都存在路径 则称此有向图为强连通图 有向图中的极大强连通子图称作有向图的强连通分量 A B C F 一个连通图的生成树是一个极小连通子图 它含有图中全部顶点 但只有足以构成一棵树的n 1条边 B C F E 如果在一棵生成树中添加一条边 必定构成一个环 一棵有n个顶点的生成树有且仅有n 1个边一个图有n个顶点和小于n 1条边 则是非连通图如果多于n 1条边 则一定有环有n 1条边的图不一定是生成树 B C F E 一个有向图的生成森林由若干棵有向树组成 含有图中全部顶点 但只有足以构成若干棵不相交的有向树的弧 有向图及其生成森林 结构的建立和销毁 插入或删除顶点 对邻接点的操作 对顶点的访问操作 遍历 插入和删除弧 基本操作 CreatGraph G V VR 按V和VR的定义构造图 DestroyGraph G 销毁图 结构的建立和销毁 对顶点的访问操作 LocateVex G u 若G存在 u和G中顶点有相同特征 若存在u 则返回该顶点在图中 位置 否则返回其它信息 GetVex G v 返回v的值 PutVex 对v赋值value 对邻接点的操作 FirstAdjVex G v 返回v的第一个邻接点 若该顶点 在G中没有邻接点 则返回 空 NextAdjVex G v w 返回v的 相对于w的 下一个邻接 点 若w是v的最后一个邻接点 则 返回 空 插入或删除顶点 InsertVex 在图G中增添新顶点v DeleteVex 删除G中顶点v及其相关的弧 插入和删除弧 InsertArc 在G中增添弧 若G是无向的 则还增添对称弧 DeleteArc 在G中删除弧 若G是无向的 则还删除对称弧 遍历 DFSTraverse G Visit 深度优先遍历图G 并对每个顶点调用 函数Visit一次且仅一次 一旦visit 失败 则操作失败 BFSTraverse G Visit 广度优先遍历图G 并对每个顶点调 用函数Visit一次且仅一次 一旦visit 失败 则操作失败 一 数组 邻接矩阵 表示法 二 邻接表 三 有向图的十字链表 四 无向图的邻接多重表 7 2图的存储结构 一 数组 邻接矩阵 表示法 无向图的邻接矩阵用两个数组分别存储顶点的信息和顶点之间关系 B A C D F E 为对称矩阵 ABCDEF ABCDEF 利用邻接矩阵容易判定两个顶点间是否有边相连 无向图中 顶点vi的度是邻接矩阵第i行 或第j列 元素之和 有向图的邻接矩阵 为非对称矩阵 ABCDE ABCDE 对于有向图 第i行元素之和为顶点vi的出度 第j列元素之和为顶点vj的入度 有向网的邻接矩阵 A i j wi j若或 vi vj VR 反之 typedefstructArcCell 弧的定义VRTypeadj VRType是顶点关系类型 对无权图 用1或0表示相邻否 对带权图 则为权值类型 InfoType info 该弧相关信息的指针 ArcCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM defineINFINITYINT MAX 最大值 defineMAX VERTEX NUM20 最大顶点个数Typedefenum DG DN UDG UDN GraphKind 有向图 有向网 无向图 无向网 图的数组 邻接矩阵 存储表示 typedefstruct 图的定义VertexTypevexs MAX VERTEX NUM 顶点向量AdjMatrixarcs 邻接矩阵intvexnum arcnum 图的当前顶点数和弧数GraphKindkind 图的种类标志 MGraph StatusCreateUDN MGraph adj info For k 0 k的权值If IncInfo Input G arcs i j info 若弧含有相关信息 则输入G arcs j i G arcs i j 置的对称弧 ReturnOK CreateUDN typedefstructArcNode 弧的结点结构intadjvex 该弧所指向的顶点的位置structArcNode nextarc 指向下一条弧的指针InfoType info 该弧相关信息的指针 ArcNode adjvexnextarcinfo 表结点结构 defineMAX VERTEX NUM20 邻接点域链域数据域 二 图的邻接表 typedefstructVNode 顶点的结点结构VertexTypedata 顶点信息ArcNode firstarc 指向第一条依附该顶点的弧的指针 VNode AdjList MAX VERTEX NUM datafirstarc 头结点结构 数据域链域 typedefstruct 图的结构AdjListvertices intvexnum arcnum 图的当前顶点数和弧数intkind 图的种类标志 ALGraph 图的结构 0A1B2C353D254E015F123 B A C D F E 无向图的邻接表 邻接点域链域 数据域链域 1 4 045 顶点vi的度恰为第i个链表中的结点数 如何求某结点的度 14 2 3 01 2 01234 ABCDE 有向图的邻接表 A B E C D 可见 在有向图的邻接表中不易找到指向该顶点的弧 入弧 求入度需遍历整个邻接表 邻接点域链域 数据域链域 如果求入度 A B E C D 有向图的逆邻接表 ABCDE 01234 在有向图的逆邻接表中 对每个顶点 链接的是指向该顶点的弧 入弧 邻接点域链域 数据域链域 三 有向图的十字链表 弧结点结构 弧尾顶点位置弧头顶点位置弧的相关信息 指向弧头相同的下一条弧 typedefstructArcBox 弧的结构表示inttailvex headvex 该弧的尾和头结点的位置structArcBox hlink tlink 分别为弧头相同和弧尾相同的弧的链域InfoType info 该弧相关信息的指针 ArcBox defineMAX VERTEX NUM20 指向弧尾相同的下一条弧 顶点的结点结构 顶点信息数据 指向以该顶点为弧头的第一个弧结点 指向以该顶点为弧尾的第一个弧结点 typedefstructVexNode 顶点的结构表示VertexTypedata ArcBox firstin firstout 分别指向该顶点第一条入弧和出弧 VexNode typedefstruct VexNodexlist MAX VERTEX NUM 表头向量intvexnum arcnum 有向图的当前顶点数和弧数 OLGraph 有向图的结构表示 四 无向图的邻接多重表 typedefstructEbox VisitIfmark 访问标记intivex jvex 该边依附的两个顶点的位置structEBox ilink jlink 分别指向依附这两个顶点的下一条边InfoType info 该边信息指针 EBox 边的结点结构 typedefstruct 邻接多重表VexBoxadjmulist MAX VERTEX NUM intvexnum edgenum 无向图的当前顶点数和边数 AMLGraph typedefstructVexBox VertexTypedata EBox firstedge 指向第一条依附该顶点的边 VexBox 顶点的结点结构 无向图的结构表示 深度优先搜索 广度优先搜索 图的遍历 从图中某一顶点出发访遍图中其余顶点 且使每个顶点仅被访问一次 图的遍历算法是求解图的连通性问题 拓扑排序和关键路径等算法的基础 7 3图的遍历 一 深度优先搜索 连通图的深度优先搜索遍历 从图中某个顶点V出发 访问此顶点 然后依次从V的未被访问的邻接点出发深度优先遍历图 直至图中所有和V有路径相通的顶点都被访问到 若此时图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 重复上述过程 直至图中所有顶点都被访问到为止 V1 V2 V3 V4 V5 V6 V7 V8 深度优先搜索顶点访问序列 V1 v2 v4 v8 v5 v3 v6 v7 1 从深度优先搜索遍历连通图的过程类似于树的先根遍历 解决的办法是 设一个辅助数组visited 0 n 1 初始值为 假 或者零 一旦访问了顶点vi 便置visited i 为 真 或者为被访问时的次序号 2 如何判别V的邻接点是否被访问 voidDFSTraverse GraphG Status Visit intv 对图G作深度优先遍历 VisitFunc Visit 使用全局变量VisitFunc 使DFS不必设函数指针参数for v 0 v G vexnum v visited v FALSE 访问标志数组初始化for v 0 v G vexnum v if visited v DFS G v 对尚未访问的顶点调用DFS Booleanvisited MAX 访问标志数组Status VisitFunc intv 函数变量 voidDFS GraphG intv 从顶点v出发递归地深度优先遍历图Gvisited v TRUE VisitFunc v 访问第v个顶点for w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS G w 对v的尚未访问的邻接顶点w递归调用DFS DFS 访问序列 v1 v2 v4 v8 v5 v3 v6 v7 首先将图中每个顶点的访问标志设为FALSE 之后搜索图中每个顶点 如果未被访问 则以该顶点为起始点 进行深度优先搜索遍历 否则继续检查下一顶点 非连通图的深度优先搜索遍历 a b c h d e k f g FFFFFFFFF T T T T T T T T T a c h d k f e b g a c h k f e d b g 访问标志 访问次序 例如 012345678 二 广度优先搜索 从图中的某个顶点V出发 并在访问此顶点之后依次访问V的各个未曾访问过的邻接点 之后按这些顶点被访问的先后次序依次访问它们的邻接点 直至图中所有和V有路径相通的顶点都被访问到 若此时图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 重复上述过程 直至图中所有顶点都被访问到为止 V w1 w8 w3 w7 w6 w2 w5 w4 对连通图 从起始点V到其余各顶点必定存在路径 其中 V w1 V w2 V w8的路径长度为1 V w7 V w3 V w5的路径长度为2 V w6 V w4的路径长度为3 w1 V w2 w7 w6 w3 w8 w5 w4 V1 V2 V3 V4 V5 V6 V7 V8 广度优先搜索顶点访问序列 V1 v2 v3 v4 v5 v6 v7 v8 voidBFSTraverse GraphG Status Visit intv 按广度优先非递归遍历图Gfor v 0 v G vexnum v visited v FALSE 初始化访问标志数组InitQueue Q 置空的辅助队列Q 接下页 For v 0 v 0 w NextAdjVex G u w if visited w w为u的尚未访问的邻接顶点visited w TRUE visit w EnQueue Q w 访问的顶点w入队列 if while if BFSTraverse 队列Q v1 v2 v3 v4 v5 v6 v7 v8 一 无向图的连通分量和生成树 对无向图进行遍历时对于连通图 从任一顶点出发 进行深度优先搜索或广度优先搜索 便可访问图中所有顶点 对于非连通图 则需从多个顶点出发进行搜索 每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集 7 4图的连通性问题 每个连通分量中的顶点集 和遍历时走过的边一起构成若干棵生成树 这些连通分量的生成树组成非连通图的生成森林 从图中任一顶点出发遍历图时 将边集分为两个集合 其中一个是遍历图过程中历经的边的集合 另一个是剩余边的集合 顶点集和遍历图过程中历经的边的集合构成连通图的极小连通子图 它是连通图的一棵生成树 非连通图 连通图 连通图 连通图 A B L M C F D E G H J K I 非连通图 A B L M C F J 邻接表存储结构参照教材P171图7 14 VoidDFSForest GraphG CSTree 建立以p为根的生成树 DFSForest 假设以孩子兄弟链表作生成森林的存储结构 建立无向图G的深度优先生成森林的孩子兄弟链表 T p q VoidDFSTree GraphG intv CSTree 从第w个顶点出发深度优先遍历图G 建立子生成树q if DFSTree 从第v个顶点出发深度优先遍历图G 建立以T为根的生成树 A B L M C F D E G H J K I T 二 最小生成树 连通网 问题 假设要在n个城市之间建立通信联络网 则连通n个城市只需要修建n 1条线路 如何在最节省经费的前提下建立这个通讯网 n个城市之间 最多可能设置n n 1 2条线路 在这些线路中选n 1条 使总的耗费最少 构造网的一棵最小生成树 即 在n n 1 2条带权的边中选取n 1条边 不构成回路 使 权值之和 为最小 该问题等价于 对于n个顶点的连通网可以建立许多不同的生成树 每一棵生成树可以是一个通信网 现在我们要选取这样一棵树 使总耗费最少 即树上各边代价之和最小 算法二 克鲁斯卡尔算法 Kruskal 算法一 普里姆算法 Prim 取图中任意一个顶点v作为生成树的根 之后往生成树上添加新的顶点w 在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边 并且该边的权值在所有连通顶点v和w之间的边中取值最小 之后继续往生成树上添加顶点 直至生成树上含有n个顶点为止 普里姆算法的基本思想 在生成树的构造过程中 图中n个顶点分属两个集合 已落在生成树上的顶点集U和尚未落在生成树上的顶点集V U 则应在所有连通U中顶点和V U中顶点的边中 非本集合内部的边 选取权值最小的边 一般情况下所添加的顶点应满足下列条件 U V U 所得生成树权值和 14 8 3 5 16 21 67 a c d f b e U V U g a b c d e g f 19 5 14 18 27 16 8 21 3 a e 12 d c b g f 7 14 8 5 3 16 21 设置一个辅助数组 对当前V U集中的每个顶点 记录和顶点集U中顶点相连接的代价最小的边 struct VertexTypeadjvex 顶点集U中顶点VRTypelowcost 边的权值 closedge MAX VERTEX NUM a b c d e g f 19 5 14 18 27 16 8 21 3 a e 12 d c b 7 a a a 19 14 18 14 例如 e 12 e e 8 16 8 d 3 d d 7 21 3 c 5 5 abcdefg g f 书上P174图7 17第一行标注出序号1 5对应结点 voidMiniSpanTree P MGraphG VertexTypeu 用普里姆算法从顶点u出发构造网G的最小生成树k LocateVex G u for j 0 j G vexnum j 辅助数组初始化if j k closedge j u G arcs k j adj closedge k lowcost 0 初始 U u for i 1 i G vexnum i MiniSpanTree 继续向生成树上添加顶点 k minimum closedge 求出加入生成树的下一个顶点 k printf closedge k adjvex G vexs k 输出生成树上一条边closedge k lowcost 0 第k顶点并入U集for j 0 j G vexnum j 修改其它顶点的最小边if G arcs k j adj closedge j lowcost closedge j G vexs k G arcs k j adj 具体做法 先构造一个只含n个顶点的子图SG 然后从权值最小的边开始 若它的添加不使SG中产生回路 则在SG上加上这条边 如此重复 直至加上n 1条边为止 考虑问题的出发点 为使生成树上边的权值之和达到最小 则应使生成树中每一条边的权值尽可能的小 克鲁斯卡尔算法的基本思想 a b c d e g f 19 5 14 18 27 16 8 21 3 a e 12 d c b g f 7 14 8 5 3 16 21 例如 7 12 18 19 普里姆 克鲁斯卡尔 时间复杂度 O n2 O eloge 稠密图 稀疏图 算法名 适应范围 比较两种算法 与网中边数无关 三 关节点 割点 和重连通分量 若连通图中的某个顶点和其相关联的边被删去之后 该连通图被分割成两个或两个以上的连通分量 则称此顶点为关节点 没有关节点的连通图为重连通图 若在连通图上至少删去k个顶点才能破坏图的连通性 则此图的连通度为k 关节点和重连通在实际中有较多应用 一个通信网络图的连通度越高 系统可靠性越高 无论哪个站点发生故障都不影响正常工作一个重连通的航空网 某条航线因天气原因关闭时 旅客仍可从其他航线绕行集成电路中关键路径设计成重连通 某些元件失效情况下不影响整个芯片工作 如何判别给定的连通图是否是重连通图 若从一个连通图中删去任何一个顶点v以及和v相关联的各边 它仍为一个连通图的话 则该连通图被称为重连通图 a b c d e f g h 哪个是关节点 顶点a和顶点c是关节点此图不是重连通图 深度优先生成树 关节点有何特征 假设从某个顶点V出发对连通图进行深度优先搜索遍历 则可得到一棵深度优先生成树 树上包含图的所有顶点 需借助图的深度优先生成树来分析 若生成树的根结点有两个或两个以上的分支 则此顶点 生成树的根 必为关节点 对生成树上的某个非叶子顶点v 其某棵子树 只要有一棵 的根和子树中的其它结点均没有指向v的祖先的回边 则v为关节点 P177 找回边是关键回边个数 图的边数 树的分支数 右图所示的关节点有哪些 Step1 求出深度优先生成树 Step2 比照原图画出回边 Step3 根据上述寻找原则找出关节点 有4个关节点A B D G 对上述两个判定准则在算法中如何实现 1 设V0为深度优先遍历的出发点p G vertices 0 firstarc v p adjvex DFSArticul G v p指向以v0为弧尾的弧结点 有向图 或p指向依附于v0的边结点 v是v0的邻接点 从第v顶点出发深度优先查找关节点if count G vexnum 生成树的根有至少两棵子树printf 0 G vertices 0 data 根是关节点 输出 2 定义函数 low v Min visited v low w visited k 其中 顶点w是生成树上顶点v的孩子 顶点k是生成树上和顶点v由回边联接的祖先 visited记录深度优先遍历时的访问次序 若对顶点v 在生成树上存在一个子树根w 且low w visited v 则顶点v为关节点 对深度优先遍历算法作如下修改 1 visited v 的值改为遍历过程中顶点的访问次序count值 2 遍历过程中求得low v Min visited v low w visited k 3 从子树遍历返回时 判别low w visited v VoidFindArticul ALGraphG count 1 visited 0 1 设定邻接表上0号顶点为生成树的根for i 1 iadjvex DFSArticul G v 从第v顶点出发深度优先查找关节点 求关节点的算法 接下页 if countnextarc p p nextarc v p adjvex if visited v 0 DFSArticul G v 从第v顶点出发深度优先查找关节点 while if FindArticual for p G vertices v0 firstarc p p p nextarc voidDFSArticul ALGraphG intv0 从第v0个顶点出发深度优先遍历图G 查找并输出关节点 visited v0 min count v0是第count个访问的顶点 并设low v0 的初值为min 检查v0的每个邻接点 low v0 min DFSArticul w p adjvex w为v0的邻接顶点if visited w 0 w未曾被访问DFSArticul G w 返回前求得low w else if low w min min low w v0的孩子结点w 存在回到祖先的回边 if low w visited v0 printf v0 G vertices v0 data 输出关节点 if visited w min min visited w w已访问 w是v0在生成树上的祖先 v0是叶子 low v Min visited v low w visited k 判别low w visited v 定义 无环的有向图 7 5有向无环图及其应用 检查有向图是否存在环 从有向图上某个顶点v出发的遍历 在dfs结束之前出现一条从顶点u到顶点v的回边 由于u在生成树是v的子孙 则有向图中必存在包含顶点v和u的环 用途一 描述含有公共子式的表达式的有效工具 实现对相同子式的共享 节省存储空间 例子见p179图7 23 用途二 有向无环图是描述工程或系统的进行过程的有效工具 几乎所有工程都可分为若干个称为活动的子工程 而这些子工程之间 通常受着一定条件的约束 如某些子工程的开始必须在另一子工程完成之后 关心两方面问题 1 工程能否顺利进行 2 估算整个工程完成必须的最短时间 拓扑排序 由某个集合上的一个偏序得到该集合上的一个全序由偏序定义得到拓扑有序 全序 的操作 用顶点表示活动 弧表示活动间的优先关系的有向图称为顶点表示活动的网 简称AOV 网 一个表示偏序的有向图可用来表示一个流程图 或者是一个施工流程图 或者是一个产品生产的流程图 或是一个数据流图 图中每一条有向边表示两个子工程之间的次序关系 领先关系 问题 假设以有向图表示一个施工流程图 或者是一个产品生产的流程图 或是一个数据流图 则图中不允许出现回路 检查有向图中是否存在回路的方法之一 是对有向图进行拓扑排序 何谓 拓扑排序 对有向图进行如下操作 按照有向图给出的次序关系 将图中顶点排成一个线性序列 对于有向图中没有限定次序关系的顶点 则可以人为加上任意的次序关系 由此所得顶点的线性序列称之为拓扑有序序列 如何进行拓扑排序 Step1 从有向图中选取一个没有前驱的顶点 并输出之 重复上述两步 直至图空 或者图不空但找不到无前驱的顶点为止 Step2 从有向图中删去此顶点以及所有以它为尾的弧 a b c g h d f e a b h c d g f e 为避免每次都要搜索入度为零的顶点 在算法中设置一个 栈 以保存 入度为零 的顶点 没有前驱的顶点 入度为零的顶点 删除顶点及以它为尾的弧 弧头顶点的入度减1 在算法中需用定量的描述替代定性的概念 StatusTopologicalSort ALGraphG 有向图G采用邻接表存储结构 若G无回路 则输出G的顶点的一个拓扑序列并返回 OK 否则ERROR FindInDegree G indegree 对各顶点求入度indegree 0 vernum 1 InitStack S for i 0 i G vexnum i 建零入度顶点栈Sif indegree i Push S i 入度为零的顶点入栈 count 0 对输出顶点计数while StackEmpty S Pop S i printf i G vertices i data count 输出i号顶点并计数for p G vertices i Firstarc p p p nextarc k p adjvex 对i号顶点的每个邻接点的入度减1if indegree k Push S k 若入度为零 则入栈 for whileif count G vexnum returnERROR 该有向图有回路elsereturnOK TopologicalSort 14 2 AB datafirstarc adjvexnextarc A B 01 关键路径 与AOV 网相对应的是AOE 网 即边表示活动的网 AOE 网是一个带权的有向无环图 其中 顶点表示事件 弧表示活动 权表示持续的时间 假设有一个有向网 表示施工流图 顶点表示事件 子工程开始或完成 弧表示活动 子工程 权表示活动持续的时间 完成该项子工程所需时间 问 哪些子工程是 关键工程 即 哪些子工程将影响整个工程的完成期限 问题 a b c d e f g h k 6 4 5 2 1 1 8 7 2 4 4 例如 源点 汇点 6 1 7 4 活动ab表示一个子工程 事件a表示这个子工程开始 事件b表示这个子工程完成 权值 表示这个子工程持续的时间 事件b还表示活动be 另一个子工程 的开始 完成工程的最短时间 从有向图的源点 入度为零的顶点 到汇点 出度为零的顶点 的最长路径的长度 关键活动 关键路径上的所有活动是关键活动 关键路径 路径长度最长的路径 如何求关键活动 计算公式 ve 源点 0 ve k Max ve j dut j k ai 事件 顶点 的最早发生时间ve k ve k 从源点到顶点k的最长路径长度 计算公式 vl 汇点 ve 汇点 vl j Min vl k dut j k ai 事件 顶点 的最迟发生时间vl j vl j 从顶点j到汇点的最短路径长度 假设第i条弧为则对第i项活动而言 活动ai 弧 的最早开始时间e i e i ve j 活动ai 弧 的最迟开始时间l i l i vl k dut j k ai a b c d e f g h k 6 4 5 2 1 1 8 7 2 4 4 0 0 0 0 0 0 0 0 0 6 4 5 7 14 7 15 18 18 18 18 18 18 18 18 18 18 16 14 7 6 6 10 8 0 拓扑有序序列 a d f c b e h g k 18 0 0 6 4 5 7 7 15 14 18 18 14 16 10 7 8 6 6 0 0 0 0 6 4 5 7 7 7 15 14 14 16 0 2 3 6 6 8 8 7 10 1 2 3 4 5 6 3 2 2 4 2 3 3 1 算法的实现要点 求ve的顺序应该是按拓扑有序的次序 而求vl的顺序应该是按拓扑逆序的次序 因为拓扑逆序序列即为拓扑有序序列的逆序列 因此在拓扑排序的过程中 另设一个 栈 记下拓扑有序序列 StatusTopologicalOrder ALGraphG Stack 初始化 while StackEmpty S Pop S j Push T j count j号顶点入T栈并计数for p G vertices j firstarc p p p nextarc k p adjvex 对j号顶点的每个邻接点的入度减1if indegree k 0 Push S k 若入度减为零则入栈if ve j p info ve k ve k ve j p info for p info dut whileif count G vexnum returnERROR 该有向网有回路elsereturnOK TopologicalOrder StatusCriticalPath ALGraphG G为有向图 输出G的各项关键活动if TopologicalOrder G T returnERROR 有回路vl 0 G vexnum 1 ve G vexnum 1 初始化顶点事件的最迟发生时间while StackEmpty T 按拓扑逆序求各顶点的vl值for Pop T j p G vertices j firstarc p p nextarc k p adjvex dut p info dutif vl k dut vl j vl j vl k dut for for j 0 jnextarc k p adjvex dut p info ee ve j el vl k dut tag ee el printf j k dut ee el tag 输出关键活动 CriticalPath 用图的结构表示交通网络 图中顶点表示城市 边表示城市间的交通联系 这个咨询系统可以回答各种问题 例如旅客希望选择交通费用最少的路线 司机希望选择距离最短的路线 为了在图中表示有关信息 可对边赋以权 权值表示两城市间的距离 时间或交通费用 路径长度的度量不是路径上边的数目 而是路径上边的权值之和 下面讨论两种最常见的最短路径问题 7 6最短路径 从某个源点到其余各顶点的最短路径 迪杰斯特拉算法 每一对顶点之间的最短路径 弗洛伊德算法 求从源点到其余各顶点的最短路径的算法的基本思想 依路径长度递增的次序产生最短路径 迪杰斯特拉 Dijkstra 算法 在这条路径上 必定只含一条弧 假设这条弧的权值最小 v1加到最短路径终点集当中 长度最短的最短路径 它只可能有两种情况 或者是直接从源点v0到另一点v2 只含一条弧 或者是从源点经过顶点v1 而最后到达v2的路径 由两条弧组成 下一条长度次短的最短路径 其余最短路径 它可能有三种情况 或者是直接从源点v0到该点 只含一条弧 或者是从源点经过顶点v1 再到达该顶点 由两条弧组成 或者是从源点经过顶点v2 再到达该顶点 它或者是直接从源点到该点 只含一条弧 或者是从源点经过已求得最短路径的顶点 再到达该顶点 再下一条长度次短的最短路径 求最短路径的迪杰斯特拉算法 设置辅助数组D 其中每个分量D i 表示当前所求得的从源点到其余各顶点vi的最短路径的长度 D i 或者 1 在所有从源点出发的弧中选取一条权值最小的弧 即为第一条最短路径 V0和Vk之间存在弧 V0和Vk之间不存在弧 其中的最小值即为最短路径的长度 设S为已找到从源点出发的最短路径的终点的集合 初始状态为空集 选择vj