图

这是一篇关于图的思维导图，主要内容包括：基本应用，遍历，存储以及基本操作，基本概念。介绍详细，描述全面，希望对感兴趣的小伙伴有所帮助！

图

• 基本概念
  • 定义和基本术语
    • 定义
    • 基本术语
      • 弧
      • 有向和无向
        • 有向图
          • 完全有向图
        • 无向图
          • 完全无向图
      • 稀疏和稠密
        • 稀疏图
        • 稠密图
      • 子图和生成子图
        • 子图
        • 生成子图
      • 顶点
        • 临接
        • 度、入度、出度
          • 度
          • 入度
          • 出度
      • 路径
        • 路径长度
        • 简单路径
        • 回路和简单回路
      • 连通图
        • 连通图的强弱
          • 连通图和图的分量
            • 连通图
            • 图的分量
          • 强连通图和强连通分量
        • 连通图的生成树
      • 生成森林
• 存储以及基本操作
  • 存储
    • 分类
      • 邻接矩阵
        • 基本思想
        • 存储方法
          • 无向无权图的邻接矩阵
          • 无向带权图的邻接矩阵
          • 有向无权图的临接矩阵
          • 有向带权图的临接矩阵
      • 邻接表
        • 链式存储结构
        • 基本思想
          • 对图的每个顶点建立一个单链表
          • 存储该顶点及其相关信息
          • 每一个单链表设一个表头节点
      • 十字链表
        • 链式存储结构
        • 域
          • data域
          • 尾域
          • 头域
          • Info域
          • 指针域
            • 指针域firstin
            • 指针域firstout
            • 指针域hlink
            • 指针域tlink
      • 邻接多重表
        • 链式存储结构
        • 域
          • data域
          • 标志域mark
          • ivex域
          • jvex域
          • 指针域
            • 指针域firstedge
            • 指针域ilink
            • 指针域jlink
  • 基本操作
    • 独立于图的存储结构
• 遍历
  • 分类
    • 深度优先搜索
      • 树的先序遍历的推广
    • 广度优先搜索
  • 思想
    • 广度优先搜索
      • 设初始状态时图中的所有顶点未被访问
• 基本应用
  • 最小生成树
  • 克鲁斯卡尔算法
  • 最短路径
    • 单源点
      • 算法思想
      • 算法实现
    • 每对顶点间
      • 算法思想
      • 算法实现
  • 拓扑排序
  • 关键路径