第六章 图

王道数据结构第六章听课笔记，内容详实、条理清晰、易于理解，无论是初学者还是准备参加考试的学生，这张脑图都将是你不可或缺的学习助手。

图

• 图的基本概念
• 图的存储
• 图的基本操作
  • 1、考研重点是邻接表与邻接矩阵这两种，尖括号表示有向边，圆括号表示无向边。
• 图的遍历
  • 广度优先遍历（BFS）
    • 类似于树的层序遍历（广度优先遍历）
      • 树
        • 不存在“回路”，搜索相邻结点时，不可能搜到已访问过的结点
        • 树的广度优先遍历（层序遍历）
          • 1、若树非空，则根节点入队
          • 2、若队列非空，则队头元素出队并访问，同时将该元素的孩子依次入队
          • 3、重复2步骤，直到队列为空
      • 图
        • 搜索相邻结点时有可能搜索到已访问过的顶点
    • 算法实现(初级)
      • 实现要点
        • 找到与一个顶点相邻的所有顶点
        • 标记哪些顶点被访问过（visited数组防止重复访问）
        • 需要一个辅助队列
        • 如何处理非连通图
      • 逻辑结构（示例）
      • 存储结构（示例）
      • 代码实现
        • 1、 将visited访问标记数组全部初始化为false（false表示未访问过，true表示已访问过） 2、 广度优先遍历开始，假设初始顶点为2，访问2顶点，并对其做出已访问标记，即visited数组下标2处标记为true 3、 顶点2入队列Q 4、 开始进入循环，若队列非空，则不断进行循环 5、 循环体内部： a、顶点2出队列； b、进行for循环，首先找到顶点2的第一个相邻顶点1，而后判断其是否被访问过，若没有则访问该顶点，并将其标 记为true，随后送入队尾Q；若是访问过，则跳过if语句直接继续循环，查找其下一个相邻结点。直到将顶点2的所有相邻顶点查找完毕才退出否语句。（在查找过程，true的顶点直接跳过，false的访问标记进队列）。 6、 所以跳出for循环后，此时队列为依次是顶点1，6 7、 队列Q非空顶点1出队，即v=顶点1，并再此进入for循环，找到与顶点1相邻的所有顶点，true的跳过，false的依次进入队尾。 8、 重复5（或6，7）步骤，直到队列Q为空跳出while循环，程序结束，全false变全true
      • 结果
        • 从顶点2出发得到的广度优先遍历序列
          • 21653748
        • 从顶点1出发得到的广度优先遍历序列
          • 12563748
        • 从顶点3出发得到的广度优先遍历序列
          • 34678215
    • 算法实现（改进）
      • 初级算法存在问题
        • 如果是非连通图，则无法遍历完所有结点
      • 代码实现（Final版）
        • 1、void BFSTraverse（Graph G）内部解析，首先调用一个for循环，对访问数组visited进行初始化（全置为false） 2、初始化一个辅助队列Q 3、再通过一个for循环遍历图G各个顶点，若是该顶点false，则以该点为出发点调用BFS（）函数，开始广度优先遍历；若是该顶点为true，则直接跳过。（这个for循环很好的解决了上一个算法无法遍历非连通图全部顶点的问题）
    • 遍历序列的可变性
      • 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一
      • 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一
    • 复杂度分析
      • 空间复杂度——辅助队列
        • 最坏情况，辅助队列大小为O（|V|）
      • 时间复杂度
        • 算法复杂度的分析不要钻到代码里去，分析其逻辑结构比较简单
        • 访问结点的时间+访问所有边的时间
        • 邻接矩阵：O（|V|^2）
        • 邻接表：O(|V|+|E|)
    • 广度优先生成树
      • 由广度优先遍历确定的树
      • 邻接表存储的图表示方式不唯一，遍历序列，生成树也不唯一
      • 遍历非连通图可得广度优先生成森林
      • 图向广度优先生成树的转化口诀
        • 顶点为根，邻点为子（该邻点未被访问过）
      • 例题1
      • 例题2
    • 总结
      • 无论是广度优先遍历额序列，还是广度优先生成树或者森林，其最终结果与图的存储结构是有关系的，存储结构不同，可能导致的结果也不相同
      • 树本身也是一种特殊的图
      • 有向图的BFS算法分析过程可以借鉴非连通图的BFS算法
  • 深度优先遍历（DFS）
    • 算法实现（初级）
      • 算法要点
        • 递归地深入探索未被访问过的邻接点（类似于树先根遍历的实现）
          • 树的先根遍历
        • 如何从一个结点找到与之邻接的其他顶点
        • visited数组防止重复访问
        • 如何处理非连通图
      • 代码实现
        • 1、 申请一个visited数组，并将其内部元素全部初始化为false 2、 函数DFS 3、 访问起始顶点V，这里定为顶点2 4、 修改顶点2的访问标记，置为true 5、 For循环，从小到大（查找顺序是依据图的存储结构而定的，并非所有情况均是从小到大，具体情况具体分析）依次查找顶点2的邻接顶点。 6、 依次判断该邻接顶点是否被访问过，true则直接跳过，false则以该邻接顶点作为起始顶点调用DFS函数（调用本身），发生递归，需要辅助栈的帮助。 7、 若是该顶点没有邻接顶点，则for循环结束，返回上一层DFS函数 8、 重复3~6步骤（重复的唯一不同便是起始访问顶点不同。），直到所有顶点均被访问完，整个程序结束。(此算法非连通图除外)
      • 结果
        • 从顶点2出发的深度优先遍历序列
          • 21563478
        • 从顶点3出发的深度优先遍历序列
          • 34762158
        • 从顶点1出发的深度优先遍历序列
          • 12634785
    • 算法实现（改进）
      • 初级算法存在问题
        • 如果是非连通图，则无法遍历完所有顶点
      • 代码实现
        • 1、void DFSTraverse（Graph G）内部解析，首先调用一个for循环，对访问数组visited进行初始化（全置为false） 2、再通过一个for循环遍历图G各个顶点，若是该顶点false，则以该点为出发点调用DFS（）函数，开始深度优先遍历；若是该顶点为true，则直接跳过。（这个for循环很好的解决了上一个算法无法遍历非连通图全部顶点的问题）
    • 复杂度分析
      • 空间复杂度——来自递归工作栈
        • 最坏情况，递归深度O（|V|）
        • 最好情况，递归深度O（1）
      • 时间复杂度
        • 访问结点的时间+访问所有边的时间
        • 邻接矩阵：O（|V|^2）
        • 邻接表：O（|V|+|E|）
    • 深度优先生成树
      • 由深度优先遍历生成的树
        • 图转化为树的口诀：起点为根，邻点为子
      • 邻接表存储图的表示方式不唯一，深度优先遍历序列，生成树也不唯一
        • 例题1
      • 深度优先遍历非连通图可得深度优先生成森林
    • 图的遍历和图的连通性
      • 有向图
        • 若从起始顶点到其他所有顶点都有路径，则只需要调用一次DFS/BFS函数
        • 对于强连通图，从任何一顶点出发都只需调用一次DFS/BFS函数
      • 无向图
        • DFS/BFS调用次数=连通分量数
• 最小生成树
• 最短路径问题
  • 单源最短路径
    • BFS算法（无权图）
      • 无权图可视为一种特殊的带权图，只是每条边的权值都为1
      • 代码实现
        • 在原始BFS算法上增加了两个数组（图中代码似乎没有申请，不知道能不能执行），分别为d（记录各个顶点到原始顶点最短路径的长度）和path（用于记录每个顶点在这个最短路径上的直接前驱） 1、 这里起始顶点定位2，即u=2 2、 第一个for循环中将初始化d和path两个数组，分别置为无穷和-1 3、 顶点2到自己的距离记为0，并将false置为true，表示已读 4、 顶点2进入队列，开启while循环 5、 若队列不为空，一直循环 6、 对头元素u（2）出队，后通过for循环寻找与顶点u（2）的所有邻接顶点 7、 判断其邻接顶点是否已读 8、 否的话，将其所有邻接顶点的最短路径加1，并将其前驱置为u，标记已读，入队。 9、 是的话，直接跳过，进行一个for循环 10、 队列为空，程序运行结束
      • 总结
        • BFS算法的局限性
          • BFS算法求单源最短路径只适用于无权图，或者是所有边的权值都相等的图
        • 带权路径长度
          • 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
    • Dijkstra（迪杰斯特拉）算法（带权图，无权图）
      • 例题1
      • 模拟过程
        • 假设要找到V0到各个顶点的最小路径，那么首先要初始化final（表示从V0开始能否找前往其余各顶点的最小路径，刚初始化时将V0置为true，因为V0本身就是起点，所以其到自身的最短路径就是0），dist（目前为止能够找到的最短最优的一条路径，总共的长度是多少），path（用于记录每个顶点在最短路径上的直接前驱）三个数组 V0开始，到各个顶点上的最短带权路径长度 V0->V0:0 V0->V1:10 V0->V2:无穷（不可直达） V0->V3:无穷 V0->V4:5 Path数组中两个0代表V1和V4在最短路径上的直接前驱是V0 第一轮循环：遍历所有顶点，找到还没确定最短路径（标记位为false）且dist最小的顶点 经过筛选V4符合，将其置为true 检查所有邻接自V4的顶点，有：V0（true），V1（false），V2（false），V3（false），若其为final值为false，则更新dist和path信息 1、 分析：以V1为例，之前V0->V1:10(最短路径)；第一循环中发现更优路径V0->V4->V1:8 2、 8<10,则V0->V4->V1路径更优，更新dist和path数据10置8，0置4 3、 同理：V0->V4->V2:14 V0->V4->V3:7 注意：若是没有更有路径，就不必更新dist与path数据 第n轮循环同理，直到标记数组的所有false全部变为true
      • 结果
      • 时间复杂度
        • 查找还未确定的最短路径......需要n-1轮处理 每一轮又要又要扫描和自身邻接的顶点，最坏情况要扫描n次 所以整体上来说，时间复杂度O（n^2）
        • O（n^2）或O（|V|^2）
      • 缺陷
        • Dijkstra（迪杰斯特拉）算法不适用于有负权值的带权图
  • 各点间的最短路径
    • Floyd算法（带权图，无权图）
      • 掌握A矩阵与path矩阵的迭代即可，算法代码不是重点
      • 动态规划思想
        • 我们会把一个大的问题的求解步骤分为多个阶段，然后每个阶段有个递进的的关系
      • 例题1
      • 模拟过程
        • 初始：不允许其他顶点中转，最短路径 1、 设置两个初始矩阵A(-1)（左侧图的邻接矩阵），path(-1)（目前能够找到的最短路径当中两个顶点之间的中转点），由于一开始不允许有中转点，所以所有数值置为-1 #0:允许V0中转，最短路径 1、 对矩阵A（-1）每个元素进行遍历 2、 如果A（-1）[i][j]>A(-1)[i][0]+A(-1)[0][j]【即Vi->Vj的距离大于Vi->V0->Vj的距离】 3、 A（0）[i][j]= A(-1)[i][0]+A(-1)[0][j] 4、 Path(0)[i][j]=0(Vi->Vj允许V0中转) 5、 如果不满足2中条件，A(0),path（0）保持原值 6、 最后得到矩阵A（0），path（0） #1 允许V0，V1中转，最短路径 在#0的基础上可以得到矩阵A（0），path（0），随后便可对着这两个矩阵重复#0的步骤可得到A（1），path（1） #3，……,#n依次类推， 注意： 1、 A（k）表示允许V0，V1,……Vk进行中转的最短路径矩阵；path（k）是与A（k）对应的中转点矩阵。 2、 若是顶点个数为n，则从A（-1），path（-1）开始要经过n轮递推，得到A（n-1），path（n-1） 3、 该例题只体现了允许V0,V1,.....,Vk中其中一个顶点中转，而不是允许其中两个或多个顶点同时中转，这是该例题的局限性，实际上在复杂的图中是允许多个中转点同时中转的 通项： A（k-1）[i][j]>A(k-1)[i][k]+A(k-1)[k][j] A（k）[i][j]= A(k-1)[i][k]+A(k-1)[k][j] Path(k)[i][j]=k
      • 结果
      • 算法代码
      • 例题2
      • 模拟过程(与类似)
        • 考试不会考这么复杂的情况，最多四个顶点，一般三个
      • 结果
      • 算法代码
        • 暂无
      • 总结
        • Floyd算法可以用于负权值带权图
        • Floyd算法不能解决带有“负权回路”的图（有负权值的边组成的回路），这种图可能没有最短路径
          • 转的圈数越多，权值路径长度越小，无止境
        • 三种算法对比
• 有向无环图（DAG）
  • 概念
    • 若一个有向图中不存在环，则称为有向无环图，简称DAG图
  • DAG描述表达式
    • 例题，求解步骤与结果
      • 求解过程中，step4与step2同时进行
• 拓扑排序
  • 1、拓扑排序无非是找到一件事情执行的先后顺序罢了
  • AOV网
    • 顶点代表活动，有向边<Vi,Vj>表示活动Vi必须先于Vj进行
    • AOV网一定是DAG图，不能有环
    • 图解
  • 拓扑排序
    • 1、拓扑排序放到AOV网中无非就是找到做事的先后顺序 2、每一个AOV网都有一个或多个拓扑排序序列 3、当前所有顶点入度>0,说明原图存在回路 4、当前网中不存在无前驱的顶点说明有回路（即说明所有顶点都有前驱）
    • 手动执行方法
      • 1、从AOV网中选择一个没有前驱（入度为0）的顶点并输出
      • 2、从网中删除该顶点和所有以它为起点的有向边
      • 3、重复1和2直到当前的AOV网为空
    • 代码实现
      • 注意：其实对一个图进行拓扑排序的过程就是不断删除入度为0的顶点 这里省略了对两个数组（indegree[],print[]）的声明,前面一个数组用于记录当前顶点的入度，而后面这个数组则是用于记录得到的拓扑排序序列。同时还需要定义一个栈，用栈S（该栈也可以用队列和数组来代替）来保存度为0的顶点。 起始： 1、indegree数组记录各顶点（0~5）入度（0，1，0，2，2） 2、print数组全部初始化为-1 函数： bool topologicalSort 1、 初始化栈，通过for循环将所有入度为0的顶点放到栈中 2、 Count记录已经输出的顶点个数，while循环（栈S非空则一直循环） 3、 弹出栈顶元素，输出数组print用于接收（逻辑上），count+1（count起到了一个伪指针的作用） 4、 再次通过for循环找到关于输出顶点所指向的所有邻接顶点，并将它们的入度分别减1（逻辑上减1） 5、 减1之后若是入度为0，则该顶点入栈 6、 以此通过While不断循环，最后退出while循环 7、 最后若是count数值等于顶点个数，则拓扑排序成功，否则失败
      • 该例题的图是以邻接表存储的图类型
    • 时间复杂度
      • 邻接表存储
        • O（|V|+|E|）
      • 邻接矩阵存储
        • O（|V|^2）
  • 逆拓扑排序
    • 手动执行方法
      • 1、从AOV网中选择一个没有后继（出度为0）的顶点并输出
      • 2、从网中删除该顶点和所有以它为终点的有向边
      • 3、重复1和2直到当前的AOV网为空
    • 代码实现（原始算法）
      • 解释参考拓扑排序中代码实现
    • 注意
      • 邻接表后面跟的是指该点向外发射出去的边；而逆邻接表后面跟的是指向该点的边
  • 另一种实现方式
    • 用DFS实现拓扑排序/逆拓扑排序
      • 拓扑排序
        • DFS算法能否实现拓扑排序还有待研究，此问题暂且搁置，后期研究
      • 逆拓扑排序
        • 1、print（v）：DFS实现逆拓扑排序在顶点退栈前输出 2、思考：如果存在回路，则不存在逆拓扑排序序列，如何判断存在回路？
  • 性质
    • 拓扑排序、逆拓扑排序序列可能不唯一
    • 若图中有环，则不存在拓扑排序序列/逆拓扑排序序列
• 关键路径
  • AOE网
    • AOE网具有以下两个性质： 1、只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始 2、只有在进入某顶点的各有向边所代表的活动都结束时，该顶点所代表的事件才能发生 3、有些活动是可以并行进行的
    • 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销
    • 相关概念
      • 在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始
      • 也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束
      • 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
    • 与AOV网的区别
      • AOE每条路径上对应着该活动完成对应的时间开销，而AOV却没有，准确来说：AOE网 VS AOV网相当于是带权图 VS 无权图
    • 图解
  • 求解方法（重点）
    • 1、求所有事件的最早发生时间ve（）
      • eg：事件vk的最早发生时间ve（k）
        • 决定了所有从Vk开始的活动能够开工的最早时间
    • 2、求所有活动的最早发生时间e（）
      • 1、看目标活动弧尾事件最早发生时间，其值即为所求 2、求取活动最早发生时间是基于求事件最早发生时间之上的，即要想求活动最早发生时间必须得求事件最早发生时间
      • eg：活动ai的最早开始时间e（i）
        • 指该活动弧的起点所表示的事件的最早发生时间
    • 3、求所有事件的最迟发生时间vl（）
      • eg：事件vk的最迟发生时间vl（k）
        • 是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
    • 4、求所有活动的最迟发生时间l（）
      • 1、看目标活动弧头事件的最迟发生时间，其值减去目标活动所需时间即为活动最迟发生时间 2、求取活动最迟发生时间是基于求事件最迟发生时间之上的，即要想求活动最迟发生时间必须得求事件最迟发生时间
      • eg：活动ai的最迟开始时间l（i）
        • 是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差
    • 5、求所有的活动时间余量d（）
      • d(i)=0的活动就是关键活动，由关键活动可得关键路径
      • d(i)=l(i)-e(i)
  • 特性（重点）
    • 若关键活动耗时增加，则整个工程的工期将增长
    • 缩短关键活动的时间，可以缩短整个工程的工期
    • 当缩短到一定程度时，关键活动可能变成非关键活动
    • 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的