⑥图

24自用408数据结构，图是由顶点集和边集组成，其中顶点为有限非空集，边集可为空；线性表可以是空表，树可以是空树，图不能是空图。

图

• 图的基本概念
  • 定义
    • 由顶点集和边集组成，其中顶点为有限非空集，边集可为空
    • 注
      • 线性表可以是空表，树可以是空树，图不能是空图
  • 有向图
    • <1，2> 弧
  • 无向图
    • (1，2) 边
  • 简单图
    • 不存在重复的边
    • 不存在顶点到自身的边(环)
  • 多重图
    • 两个顶点之间边数大于1，且允许存在环
  • 完全图
    • 有向完全图
      • 任意两个顶点之间都有两条方向相反的弧
        • 有n(n-1)条弧的图
    • 无向完全图
      • 任意两个顶点之间都存在边
        • 有n(n-1)/2条边的图
  • 子图
    • 生成子图
      • 包含了原图所有的顶点
  • 连通图
    • 任意两个顶点都是连通的
    • 若一个图有n个顶点，边数小于n-1时，此图必是非连通图
    • 边数大于n-1，一定有环
    • 方向
      • 无向
        • 连通分量
          • 无向图中的极大连通子图(边尽可能多)
      • 有向
        • 强连通图
          • 任何一对顶点v和w，从v到w和从w到v都有路径
          • 至少需要n条边，构成环路
        • 强连通分量
          • 有向图中的极大强连通子图(边尽可能多)
    • 生成树
      • 包含连通图中全部顶点的一个极小连通子图(边尽可能少，但要保持连通)
      • 顶点数为n，边数为n-1
      • 砍去一条边则为非连通图，加上一条边则形成一个回路
  • 度
    • 依附于顶点的边的条数
      • 无向图
        • 全部顶点的度的和＝边数的2倍
      • 有向图
        • 入度＝出度＝边数
  • 网
    • 带权图称为网
  • 稠密图和稀疏图
    • 一般当图G E＜VlogV时为稀疏图
  • 一个顶点的入度为0，其余顶点的入度为1的有向图为有向树
  • 顶点不重复出现为简单路径，除第一个顶点和最后一个顶点，其余顶点不重复出出现的回路称为简单回路
• 图的存储及基本操作
  • 邻接矩阵法
    • 定义
      • 用一个一维数组存储顶点，用一个二维数组存储边(即顶点间的关系)
      • 存储顶点之间邻接关系的二维数组称为邻接矩阵
    • 空间复杂度为O(n'2)
    • 特点
      • 1| 无向图
        • 邻接矩阵为对称矩阵，存储时可采用压缩存储
        • 第i行或第i列非零元素个数为顶点的度
      • 2| 有向图
        • 第i行为顶点i的出度
        • 第i列为顶点的入度
      • 3| 容易确定顶点之间是否有边，要确定边的总数，需遍历整个矩阵，花费时间大
      • 4| 稠密图适合邻接矩阵
      • 5| A'n[i][j]＝顶点i到顶点j长度为n的路径数目
    • 
  • 邻接表法
    • 顶点表
      • 顺序存储顶点和头指针
        • 顶点域data+边表头指针firstarc
    • 边表
      • 链式存储
        • 邻接点域adjvex+指针nextarc
    • 
      • 
    • 特点
      • 1| 无向图
        • 所需存储空间O(|V|+2|E|)
      • 2| 有向图
        • 所需存储空间O(|V|+|E|)
      • 3| 稀疏图适合用邻接表
      • 4| 容易找到有一顶点的所有邻边，若需找到两个顶点之间是否有边，则效率低
      • 5| 求顶点的出度只需计算其邻接表中结点个数，求入度则需要遍历整个邻接表
      • 6| 邻接表不唯一，若确定了编号次序，则唯一
    • 
  • 十字链表
    • 十字链表是有向图的一种链式存储结构
    • 弧结点
      • 
    • 顶点结点
      • 
      • 顺着firstout可找到所有出边
      • 顺着firstin可找到所有入边
    • 图的十字链表不唯一，但十字链表确定一个图
    • 空间复杂度：O(|V|+|E|)
  • 邻接多重表
    • 邻接多重是无向图的一种链式存储方式
    • 删除操作方便
    • 边结点
      • 
    • 顶点结点
      • 
    • 对无向图而言，其邻接多重表和邻接表的差别在于，同一条边在邻接矩阵中用两个结点表示，而在邻接多重表中用一个结点表示
    • 空间复杂度：O(|V|+|E|)
• 图的遍历
  • 从图中的某一顶点出发，按照某种搜索方法沿着图中的所有顶点访问且仅访问一次
  • 广度优先遍历(BFS)
    • 类似层序遍历
    • 步骤
      • 1| 首先访问起始顶点v，接着从v出发，依次访问v的各个未访问的邻接顶点v1，v2....
      • 2| 依次访问v1，v2的所有未被访问的邻接顶点
      • 3| 再从这些访问过的顶点出发，访问他们所有未被访问过的邻接顶点，直至所有顶点都被访问过
    • 需要借助队列实现
    • 复杂度
      • 空间复杂度
        • O(|V|)
      • 时间复杂度
        • 邻接表
          • O(|V|+|E|)
        • 邻接矩阵
          • O(|V|'2)
    • 可解决单源最短路径问题
    • 广度优先生成树
      • 在广度遍历过程中，可以得到一棵遍历树，称为广度优先生成树
      • 唯一性
        • 给定图的邻接矩阵存储表示唯一，故广度优先生成树也是唯一
        • 邻接表存储表示不唯一，则其广度优先生成树也不唯一
  • 深度优先遍历(DFS)
    • 类似于树的先序遍历
    • 步骤
      • 1| 首先访问起始顶点v，接着从v出发，访问与v邻接且未被访问的任一结点v1
      • 2| 再访问与v1邻接的且未被访问的任一结点
      • 3| 重复①②，直至不能向下访问时，依次退回至最近被访问的结点
      • 4| 若它还有邻接结点未被访问，则从它开始重复①②③，直至所有结点都被访问
    • 需要借助递归工作栈
    • 复杂度
      • 空间复杂度
        • O(|V|)
      • 时间复杂度
        • 邻接表
          • O(|V|+|E|)
        • 邻接矩阵
          • O(|V|'2)
    • 深度优先生成树
      • 连通图
        • 得到深度优先生成树
      • 非连通图
        • 得到的是深度优先森林
      • 唯一性
        • 给定图的邻接矩阵存储表示唯一，故广度优先生成树也是唯一
        • 邻接表存储表示不唯一，则其广度优先生成树也不唯一
  • 基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的； 基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。
  • 图的遍历与连通性
    • 有向图
      • 若起点到其他各个顶点都有路径，则只需要调用1次BFS/DFS
      • 对于强连通图，从任一结点出发都只需调用1次BFS/DFS
    • 无向图
      • 调用BFS/DFS的次数＝连通分量的次数
      • 对于连通图，只需调用1次BFS/DFS
• 图的应用
  • 最小生成树
    • 定义
      • 生成树
        • 一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去一条边，则为非连通图，若加上一条边，则会形成环。
      • 最小生成树
        • 在带权连通无向图中，权值之和最小的生成树为最小生成树
    • 性质
      • 唯一性
        • 最小生成树不是唯一的
        • 当图G中各边权值互不相等时，G的最小生成树唯一
        • 最小生成树的边的权值之和总是唯一的
      • 自身性
        • 若无向连通图G的边数比顶点数少1，G本身是一棵树，且最小生成树为本身
      • 最小生成树的边数为顶点数减1
    • 最小生成树算法
      • Prim(普里姆)算法 选顶点
        • 
        • 时间复杂度
          • O(|V|'2)
          • 不依赖于E
        • 适用于求解边稠密的图的最小生成树
      • Kruskal(克鲁斯卡尔)算法 选边
        • 
        • 时间复杂度
          • 每次选择最小权值的边
            • 采用堆存放边的集合
              • O(log|E|)
          • 构造最小生成树
            • 采用并查集的数据结构来描述最小生成树
              • O(|E|log|E|)
        • 适合边稀疏而顶点较多的图
  • 最短路径
    • 单源最短路径
      • 广度优先遍历(BFS)
        • 无权图
      • Dijkstra算法求单源最短路径问题 选顶点，看是否缩短路径
        • 
        • 基于贪心算法
        • 不适用于边上有负权值
        • 时间复杂度
          • O(|V|'2)
    • Floyd算法求各顶点之间最短路径问题 循环顶点，看是否做桥梁
      • 
      • 不适合有负权值的回路
      • 时间复杂度
        • O(|V|′3)
    • 
  • 有向无环图描述表达式
    • DAG图
      • 若一个有向图中不存在环，则称为有向无环图
    • 
    • 不唯一
  • 拓扑排序
    • AOV网
      • 顶点表示活动，有向边表示活动先后关系
    • 对有向无环图实现
    • 不唯一
      • 每个AOV网都有一个或多个拓扑排序
    • 实现
      • DFS+栈可以实现拓扑排序
      • DFS退出递归时输出顶点的序列为逆拓扑排序
    • 可判断是否有环
      • DFS也可以
    • 
    • 时间复杂度
      • 邻接表存储
        • O(|V|+|E|)
      • 邻接矩阵存储
        • O(|V|'2)
    • 三角矩阵必有拓扑排序，拓扑排序不一定是三角矩阵
  • 关键路径
    • AOE网
      • 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销称为AOE网
      • 性质
        • 只有在某顶点所代表的事件发生之后，从该顶点出发的各有向边所代表的活动才能开始
        • 只有进入某顶点的各有向边所代表的活动都结束时，该点所代表事件才能发生
        • 分别仅有一个出度(汇点)和入度(源点)为0的顶点
    • 完成整个工程的最短时间就是关键路径的长度
    • 参量定义
      • 事件vk的最早发生时间ve(k)
        • 源点v1到顶点vk的最长路径长度
      • 事件vk的最迟发生时间vl(k)
        • 在不推迟整个工程的前提下，即保证它的后继事件vj在其最迟发生时间vl(j)能够发生时，该时间最迟必须发生的时间 从后往前推
      • 活动ai的最早开始时间e(i)
        • 活动弧的起点所表示事件的最早发生时间
      • 活动ai的最迟开始时间l(i)
        • 活动弧的终点所表示事件的最迟发生时间与该活动之差。
    • 步骤
      • 
    • 特性
      • 关键路径上的所有活动都是关键活动
      • 可以缩短关键活动，来加快工程，但缩小至一定程度，该关键活动可能会变成非关键活动
      • 关键路径不唯一，只提高一条关键路径的活动速度，并不能提高工程的速度，只有加快所有关键路径速度，才能提高工程速度