王道数据结构

王道数据结构第六章图的知识内容有基本概念、存储、广度优先搜索、深度优先搜索、最小生成树、最短路径、有向无环图、关键排序，希望梳理的内容对你有所帮助！

第6章 图

• 基本概念
  • 顶点集V、边集E
    • 顶点
      • 入度、出度、度
    • 边
      • 权值、带权图aka网
      • 稀疏图、稠密图
    • 路径（顶点+边）、路径长度（边数）、回路
      • 简单路径
      • 简单回路
      • 顶点不重复
      • 最短路径aka距离
  • 有向图、无向图
    • 有一种有向图叫做有向树
  • 简单图、多重图（有无重复边及顶点到自身的边）
  • 完全图（每个顶点间都有边）
    • |E|=n(n-1)/2
    • |E|=n(n-1)
  • 子图
    • 需包含全部顶点
  • 无向图—连通—连通图
    • 极大连通子图aka连通分量
      • 非连通图的连通分量的生成树构成生成森林
    • 极小连通子图aka生成树（含全部顶点、边少、连通）
      • n顶点，n-1边
    • 生成树、森林
  • 有向图—强连通—强连通图
    • 极大强连通子图aka强连通分量
• 存储
  • 邻接矩阵
    • 稠密图
    • T=O(|V|)
  • 邻接表
    • 稀疏图
    • 存储空间
      • 有向：O( |V+2E| )
      • 无向：O( |V+E| )
    • 有向出度T=O(|V|)
    • 不唯一
  • 十字链表（有向图）
    • 弧结点
      • 弧头、弧尾、弧头相同的下一条弧、弧尾相同的下一条弧、弧信息
    • 顶点结点
      • 顶点信息、第一个出弧结点、第一个入弧结点
    • 不唯一
  • 邻接多重表（无向图）
    • 边结点
      • 标志域（标记边是否被搜索过）、顶点1、下一条依附于顶点1的边、顶点2、下一条依附于顶点2的边、边信息
    • 顶点结点
      • 顶点信息、第一条依附于该顶点的边
    • 不唯一
• 遍历
  • 广度优先搜索BFS
    • 非递归、借助队列
    • 算法
      • 对于每个未visit过的顶点：visit之并入队； while（队非空）：【队首出栈；对其所有邻接顶点：【若未visit：visit之并入队】】
      • 空间复杂度（队列）=O( |V| )
      • 时间复杂度（每个顶点的每个邻接点）
        • 邻接矩阵：O( | V^2| )
        • 邻接表：O( |V+E| )
    • 广度优先生成树（遍历树）
      • 邻接矩阵：唯一
      • 邻接表：不唯一
  • 深度优先搜索DFS
    • 递归、借助栈
    • 算法
      • 对于每个未visit过的顶点：DFS【visit之；对其所有邻接顶点：【若未visit：DFS之】】
      • 空间复杂度（栈）=O( |V| )
      • 时间复杂度（每个顶点的每个邻接点）
        • 邻接矩阵：O( | V^2| )
        • 邻接表：O( |V+E| )
    • 深度优先生成树（遍历树）
      • 邻接矩阵：唯一
      • 邻接表：不唯一
• 应用
  • 最小生成树
    • Prim算法
      • T=O( |V|^2 )
      • 适用于边稠密
    • Kruskal算法
      • T=O( |E|log|E| )
      • 适用于边稀疏但点稠密
  • 最短路径
    • BFS求单源最短路径
      • visit: 路径长度加一，记录前一顶点
    • Dijkstra算法
      • 单源
      • T=O( |V|^2 )
      • 不允许负边
    • Floyd算法
      • 顶点之间
      • T=O( |V|^3 )
      • 允许负边，但不允许负回路
  • 有向无环图DAG
    • 描述表达式
    • 表示工程时aka AOV网
      • 拓扑排序
        • T=O( |V+E| )
  • 关键排序