图论简单介绍PPT课件.ppt

第八章图 图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径 1 拓扑排序 计划 施工过程 生产流程 程序流程等都是 工程 除了很小的工程外 一般都把工程分为若干个叫做 活动 的子工程 完成了这些活动 这个工程就可以完成了 例如 计算机专业学生的学习就是一个工程 每一门课程的学习就是整个工程的一些活动 其中有些课程要求先修课程 有些则不要求 这样在有的课程之间有先后关系 有的课程可以并行地学习 2 C1高等数学C2程序设计基础C3离散数学C1 C2C4数据结构C3 C2C5高级语言程序设计C2C6编译方法C5 C4C7操作系统C4 C9C8普通物理C1C9计算机原理C8 课程代号 课程名称 先修课程 3 学生课程学习工程图 4 可以用有向图表示一个工程 在这种有向图中 用顶点表示活动 用有向边表示活动的前后次序 Vi必须先于活动Vj进行 这种有向图叫做顶点表示活动的AOV网络 ActivityOnVertices 在AOV网络中 如果活动Vi必须在活动Vj之前进行 则存在有向边 AOV网络中不能出现有向回路 即有向环 在AOV网络中如果出现了有向环 则意味着某项活动应以自己作为先决条件 因此 对给定的AOV网络 必须先判断它是否存在有向环 5 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列 即将各个顶点 代表各个活动 排列成一个线性有序的序列 使得AOV网络中所有应存在的前驱和后继关系都能得到满足 这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序 如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中 则该AOV网络中必定不会出现有向环 相反 如果得不到满足要求的拓扑有序序列 则说明AOV网络中存在有向环 此AOV网络所代表的工程是不可行的 6 例如 对学生选课工程图进行拓扑排序 得到的拓扑有序序列为C1 C2 C3 C4 C5 C6 C8 C9 C7或C1 C8 C9 C2 C5 C3 C4 C7 C6 7 进行拓扑排序的方法 输入AOV网络 令n为顶点个数 1 在AOV网络中选一个没有直接前驱的顶点 即此顶点入度为0 并输出之 2 从图中删去该顶点 同时删去所有它发出的有向边 重复以上两步 直到全部顶点均已输出 拓扑有序序列形成 拓扑排序完成 或图中还有未输出的顶点 但已跳出处理循环 这说明图中还剩下一些顶点 它们都有直接前驱 再也找不到没有前驱的顶点了 这时AOV网络中必定存在有向环 8 a b c d e f 9 为了便于考察每个顶点的入度 在顶点表中增加一个入度域 同时设置一个栈来存储所有入度为0的顶点 在进行拓扑排序之前 只要对顶点表扫描一遍 将所有入度为0的顶点都推入栈中 一旦排序过程中出现新的入度为0的顶点 也同样将其推入栈中 出边表 10 1 扫描顶点表 将入度为0的顶点入栈 2 while 栈非空 将栈顶顶点v弹出并输出之 检查v的出边 将每条出边终点u的入度减1 若u的入度变为0 则把u推入栈 3 若输出的顶点数小于n 则输出 有回路 否则拓扑排序正常结束 拓扑排序算法框架 11 在算法具体实现时 上述链栈无须占有额外的空间 而是利用顶点表中值为0的入度域来存放链栈的指针 用下标值模拟 因为顶点域中已经存入有相应的顶点 故入栈时只需修改相应的指针 12 0 2 1 2 3 0 0 2 1 2 3 1 0 2 1 1 2 1 0 1 4 0 2 1 top top top top 0 13 0 4 4 0 1 1 0 4 4 0 1 1 0 4 4 0 0 1 0 4 4 0 0 1 top top top 14 拓扑排序算法typedefintdatatype typedefintvextype typedefstructnode 边表结点定义 intadjvex structnode next edgenode typedefstruct 顶点表结点定义 vextypevertexintid edgenode link vexnode vexnodedig n 15 TOPOSORT vexnodedig inti j k m 0 top 1 edgenode p for i 0 i n i if dig i id 0 dig i id top top i while top 1 j top top dog top id printf d t dig j vertex 1 m p dig j link while p k p adjvex dig k id if dig k id 0 dig k id top top k p p next if m n printf nThenetworkhasacycle n 16 算法分析设AOV网有n个顶点 e条边 初始建立入度为0的顶点栈 要检查所有顶点一次 执行时间为O n 排序中 若AOV网无回路 则每个顶点入 出栈各一次 每个边表结点被检查一次 执行时间为O n e 所以总的时间复杂度为O n e 17 关键路径 如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动 Activity 用边上的权值表示活动的持续时间 Duration 用顶点表示事件 Event AOE网络在某些工程估算方面非常有用 例如 可以使人们了解 1 完成整个工程至少需要多少时间 假设网络中没有环 2 为缩短完成工程所需的时间 应当加快哪些活动 则这样的有向图叫做用边表示活动的网络 简称AOE ActivityOnEdges 网络 18 在AOE网络中 有些活动顺序进行 有些活动并行进行 从源点到各个顶点 以至从源点到汇点的有向路径可能不止一条 这些路径的长度也可能不同 完成不同路径的活动所需的时间虽然不同 但只有各条路径上所有活动都完成了 整个工程才算完成 因此 完成整个工程所需的时间取决于从源点到汇点的最长路径长度 即在这条路径上所有活动的持续时间之和 这条路径长度最长的路径就叫做关键路径 CriticalPath 19 定义几个与计算关键活动有关的量 事件Vi的最早可能开始时间Ve i 是从源点V0到顶点Vi的最长路径长度 事件Vi的最迟允许开始时间Vl i 是在保证汇点Vn 1在Ve n 1 时刻完成的前提下 事件Vi的允许的最迟开始时间 活动ak的最早可能开始时间e k 设活动ak在边上 则e k 是从源点V0到顶点Vi的最长路径长度 因此 e k Ve i 活动ak的最迟允许开始时间l k l k 是在不会引起时间延误的前提下 该活动允许的最迟开始时间 20 l k Vl j dur 其中 dur 是完成ak所需的时间 时间余量l k e k 表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量 l k e k 表示活动ak是没有时间余量的关键活动 显然 关键路径上的所有活动都是关键活动 为找出关键活动 需要求各个活动的e k 与l k 以判别是否l k e k 为求得e k 与l k 需要先求得从源点V0到各个顶点Vi的Ve i 和Vl i 求Ve i 的递推公式 21 从Ve 0 0开始 向前递推 S2 i 1 2 n 1其中 S2是所有从Vi指向顶点Vj的有向边的集合 从Vl n 1 Ve n 1 开始 反向递推 S1 i n 2 n 3 0其中 S1是所有从顶点Vi发出的有向边的集合 22 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行 设活动ak k 1 2 e 在带权有向边上 它的持续时间用dur 表示 则有e k Ve i l k Vl j dur k 1 2 e 这样就得到计算关键路径的算法 计算关键路径时 可以一边进行拓扑排序一边计算各顶点的Ve i 并按拓扑有序的顺序对各顶点重新进行了编号 算法在求Ve i i 0 1 n 1时按拓扑有序的顺序计算 在求Vl i i n 1 n 2 0时按逆拓扑有序的顺序计算 23 6 4 0 5 7 7 16 14 18 18 14 10 8 6 6 16 7 0 24 25 26 求关键路径的算法typedefstructnode1 边表结点定义 intadjvex 邻接点域 intdut 权值 structnode1 next 链域 edgenode1 typedefstructnode2 顶点表结点定义 vextypevertex 顶点信息 intid 入度 edgenode1 link 边表头指针 vexnode1 vexnode1dig n 邻接表 27 CRITICALPATH vexnode1dig inti j k m intfront 1 rear 1 顺序队列首位指针置初值 inttpord n vl n ve n intl maxsize e maxsize edgenode1 p for i 0 i n i ve i 0 各事件最早发生时间置为0 for i 0 i n i 将入度为0的顶点入队 if dig i id 0 tpord rear i 28 m 0 计数器初始化 while front rear 队非空 front j tpord front 出队 m 对出队的顶点个数计数 p dig j link 指向出边表中顶点的下标 while p 删去所有出边 k p adjvex dig k id 入度减1 if ve j p dut ve k ve k ve j p dut 计算最早发生时间 if dig k id 0 tpord rear k 新的入度为0的顶点入队 p p next 找下一条边 29 if m 0 i 按拓扑序列的逆序取顶点 i tpord i p dig j link 取出边表上的第一个表结点 while p k p adjvex if vl k p dut dut p p next 找下一条边 30 i 0 边计数器置初值 for j 0 jadjvex e i ve j l i vl k p dut printf d t d t d t d t d t 输出信息 dig j vertex 1 dig k vertex 1 e i l i