数据结构之图的知识导图

以下总结了数据结构中图的知识内容，包括图的基本概念、图的存储及基本操作、图的遍历、图的应用等方面内容。

图

• 6.1图的基本概念
  • 定义: G=(V,E),顶点集V,边集E
  • 用|V|表示图G中顶点的个数也称图的阶 用|E|表示图G中边的条数
  • 无向图(无向边/边)、有向图(有向边/弧)
  • 简单图、多重图
  • 顶点的度、出度、入度(无向图？有向图？)
  • 边的权、带权图/网、权值
  • 点到点的关系
    • 路径、回路、简单路径、简单回路
    • 路径长度
    • 点到点的距离(最短路径)
    • 连通、连通图和连通分量(无向图)
      • 无向图中的极大连通子图称为连通分量
        • 从一个顶点开始作为一个子图，逐个添加好这个子图有边相连的顶点，直到所有的顶点都被纳入图中，所生成的子图就是一个极大连通子图
      • 若一个图有n个顶点，并且该边数少于n-1，则此图必是非连通图
    • 强连通图、强连通分量(有向图)
      • 若G是强连通图，则最少有n条边(形成回路)
      • 有向图中的极大强连通子图称为有向图的强连通分量
        • 当某个顶点只有出弧而没有入弧时，其他顶点无法到达这个顶点，这个单独的顶点构成一个强连通分量
  • 生成树、生成森林
    • 连通图的生成树是包含图中全部顶点的一个极小连通子图
    • 若图中顶点数为n，则它的生成树共有n-1条边
    • 对生成树而言，若砍去一条边，就会变成非连通图，若加上一条边，则会形成一个回路
    • 在非连通图中，连通分量的生成树构成了非连通图的生成森林
  • 几种特殊形态的图
    • 完全图
    • 稀疏图、稠密图
    • 树、森林、有向树
• 6.2图的存储及基本操作
  • 邻接矩阵法
    • 只要确定了顶点编号，表示唯一
    • “行入列出”准则：对于有向图而言，第i个结点的出度=第i行的非零元素个数，第i个结点的入度=第i列的非零元素个数
    • 对于无向图，第i个结点的度=第i行或第i列的非零元素个数
    • 求顶点的度的时间复杂度为O(｜V｜),空间复杂度为O(｜V｜²)
    • 适合存储稠密图，无向图的邻接矩阵是对称矩阵，可以压缩存储（只存上/下三角区)
    • 设图G的邻接矩阵为A(矩阵元素为0/1），则A∧n的元素A^n【i】【j】等于由顶点i到顶点j的长度为n的路径的数目
  • 邻接表法（顺序+链式存储）
    • 图的邻接表示方式不唯一
    • 空间复杂度
      • 无向图O(｜V｜+2｜E｜)
      • 有向图O(｜V｜+2｜E｜)
    • 存储稀疏图
    • 计算有向图的入度不方便（找有向图的入边不方便），其余很方便
  • 十字链表（有向图）
    • 弧结点和顶点结点
    • 空间复杂度O(｜V｜+｜E｜)
  • 邻接多重表（无向图)
    • 空间复杂度O(｜V｜+｜E｜)
  • 图的基本操作
• 6.3图的遍历
  • 广度优先遍历（BFS)
    • 类似于二叉树的层序遍历
    • 算法要点
      • 需要一个辅助队列
      • 如何从一个顶点找到与之相邻的其他顶点；visit数组防止重复访问
      • 如何处理非连通图
    • 复杂度
      • 空间复杂度O(｜V｜）-辅助队列
      • 时间复杂度
        • 访问结点的时间+访问所有边的时间
        • 邻接矩阵：O(｜V｜^2）
        • 邻接表：O(｜V｜+｜E｜)
    • 广度优先生成树
      • 邻接表存储的图表示方法不唯一，遍历序列、生成树也不唯一
      • 遍历非连通图可得广度优先生成森林
  • 深度优先遍历（DFS)
    • 类似于树的先序遍历，搜索策略是尽可能深地搜索一个“图”
    • 算法思想
      • 递归地深入探索未被访问过的邻接点，如何从一个顶点找到与之相邻的其他顶点；visit数组防止重复访问
      • 如何处理非连通图
    • 复杂度分析
      • 空间复杂度O(｜V｜）——来自递归工作栈
      • 时间复杂度
        • 邻接矩阵：O(｜V｜^2）
        • 邻接表：O(｜V｜+｜E｜)
    • 深度优先生成树
      • 与广度优先生成树同理
  • 图的遍历和图的连通性
    • 对于无向图
      • DFS/BFS函数调用次数=连通分量数
    • 对于有向图
      • 若从起始顶点到其他顶点都有路径，则只需要调用一次DFS/BFS函数
      • 对于强连通图，从任一顶点出发都只需要调用一次DFS/BFS函数
• 6.4图的应用
  • 最小生成树（最小代价树）
    • 定义： 边的权值之和最小的生成树（MST）
    • 最小生成树的性质
      • 最小生成树可能有多个，但边的权值之和总是唯一且最小的
      • 最小生成树的边数=顶点数-1 ；砍掉一条则不连通，增加一条则会出现回路
      • 如果一个连通图本身就是一棵树，则其最小生成树就是其本身
      • 只有连通图才有生成树，非连通图只有生成森林
      • 只要无向连通图没有权值相等的边，则其最小生成树唯一，因为用不同的算法寻找过程是唯一的
    • 最小生成树算法
      • prim算法（普里姆）
        • 概述： 从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
        • 时间复杂度O(｜V｜^2）
        • 适用于边稠密图
      • Kruskal算法（克鲁斯卡尔）
        • 每次选择权值最小的一条边(在不产生环的前提下)，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通
        • 时间复杂度：O(｜E｜log｜E｜）
        • 适用于边稀疏而顶点较多的图
  • 最短路径问题
    • 单源最短路径
      • BFS算法（无权图）
        • 就是对BFS算法的小修改，在visit一个顶点时，修改其最短路径长度d【】并在path【】记录前驱节点
        • 时间复杂度O(｜V｜^2）或O(｜V｜+｜E｜)
      • dijkstra算法（带权图、无权图）
        • 建立三个数组
          • final[ ]标记各顶点是否已找到最短路径
          • dist[ ]标记最短路径长度
          • path[ ]标记路径上的前驱
        • 算法思想: 每轮循环遍历所有结点，找到还没确定最短路径，且dist最小的顶点Vi,令final[i]=true， 检查所有邻接自Vi的顶点，若其final值为false，则更新dist 和path信息
        • 时间复杂度O(｜V｜^2）
        • 注意:该算法不适用于边上带有负权值的带权图
    • 各顶点间的最短路径
      • floyd算法（带权图、无权图）
        • 使用动态规划思想，将问题的求解分为多个阶段
          • #初始:不允许在其他顶点中转，最短路径是？
          • #0:若允许在Vo中转，最短路径是？后面一直循环
        • Floyd算法不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径
        • 时间复杂度O(｜V｜^3）
      • 也可以用dijkstra算法求所有顶点之间的最短路径，重复｜V｜次即可，总的时间复杂度也是O(｜V｜^3)
  • 有向无环图描述表达式(DAG)
    • 若一个有向图中不存在环，则称为～
    • 咸鱼解题方法
      • ①把各个操作数不重复地排成一排
      • ②标出各个运算符的生效顺序(先后顺序有点出入无所谓)
      • 按顺序加入运算符，注意“分层”
      • 从底向上逐层检查同层的运算符是否可以合体
  • 拓扑排序
    • AOV网
      • 顶点表示活动 有向边<Vi,Vj>表示活动Vi必须先于Vj进行
      • AOV网一定是DAG图，不能有环
    • 拓扑排序
      • 从AOV网中选择一个没有前驱(入度为0)的顶点并输出
      • ②从网中删除该顶点和所有以它为起点的有向边
      • ③重复①和②直到当前的AOV网为空
    • 逆拓扑排序
      • ①从AOV网中选择一个没有后继(出度为0)的结点并输出
      • 从网中删除该顶点和所有以它为终点的有向边
      • 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。(说明有回路)
      • 模仿拓扑排序的思想实现逆拓扑排序的话，注意使用邻接矩阵这种存储结构，若使用邻接表的话由于删除某个顶点得话还要删除指向该顶点的边，每次都要遍历整个表，时间复杂度很高
        • 可以用逆邻接表
    • 另一种实现方式:用DFS算法实现拓扑和逆拓扑排序(实现逆拓扑排序时，在顶点退栈前输出)
    • 性质
      • 拓扑排序、逆拓扑排序序列可能不唯一
      • 若图中有环，则不存在拓扑排序序列/逆拓扑排序序列
      • 对于一般的图来说，若其邻接矩阵是三角矩阵(不存在回路)，则存在拓扑序列；反之则不一定成立
      • 若一个有向图具有有序的拓扑排序序列，那么它的邻接矩阵必定为三角矩阵
  • 关键路径
    • AOE网
      • 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销
      • 相关概念
        • 开始顶点(源点)入度为0，表示整个工程的开始
        • 仅有一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束
        • 从源点到汇点的有向路径可能有很多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
    • 求解方法
      • ①求所有事件的最早发生时间ve( )
        • 决定了所有从vk开始的活动能够开工的最早时间
      • ②求所有事件的最迟发生时间vl( )
        • 它是指在不推迟整个工程完成的前提下，该事件最迟发生的时间
      • ③求所有活动的最早发生时间e( )
        • 指该活动弧的起点所表示的事件的最早发生时间
      • ④求所有活动的最迟发生时间l( )
        • 它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差
      • ⑤求所有活动的时间余量d( )=l( )-e( )
        • d(i)=0的活动就是关键活动，由关键活动可得关键路径
      • ①按拓扑排序序列依次求ve(k): ve(源点)=0 ve(k)=MAX｛ve(j)+Weight(vj,vk)｝,vi为vk的前驱 ②按逆拓扑序列排列求vl(k) vl(汇点)=ve(汇点) vl(k)=Min｛vl(j)-Weight(vk,vj)｝,vj为vk的任意后继
    • 特性
      • 若关键活动耗时增加，则整个工程的工期将增长
      • 缩短关键活动的时间，可以锁短整个工程的工期
      • 当缩短到一定程度时，关键活动可能会变成非关键活动
      • 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
• 主题