数据结构——图

数据结构——图思维导图，包括：图的定义和基本术语、图的遍历、图的存储结构、图的应用等内容。

数据结构——图

• 图的定义和基本术语
  • 定义
    • 是由一个顶点集V和一个顶点间的关系集合组成的数据结构
  • 分类
    • 有向图
    • 无向图
  • 基本术语
    • 有（无）向网
      • 弧或边带权的图
    • 子图
    • 完全图
      • 含有e=n(n-1)/2条边的无向图
    • 有向完全图
      • 含有e=n(n-1）条弧的有向图
    • 稀疏图
      • 边或弧的个数＜nlogn
    • 稠密图
      • 边或弧的个数＞＝nlogn
    • 度（入度＋出度）
      • 入度
        • 以顶点v为弧尾的弧的数目
      • 出度
        • 以顶点v为弧头的弧的数目
    • 路径长度
      • 路径上边的数目
    • 连通图
      • 图中任意两个顶点之间都有路径相通
• 图的遍历
  • 深度优先搜索DPS
    • 类似于先序遍历
    • 实质
      • 对每个顶点查找其邻接点的过程
  • 广度优先搜索BFS
    • 实质
      • 通过边或弧找邻接点的过程
• 图的存储结构
  • 邻接矩阵
    • 有向图：对称
      • 统计第i行1的个数可得顶点i的出度
    • 无向图：不对称
      • 统计第j列1的个数可得顶点j的入度
  • 邻接表
    • 只存储图中已有的弧或边的信息
  • 有向图的十字链表
    • 将有向图的邻接表和逆邻接表结合起来的一种链
• 图的应用
  • 最小生成树
    • 普里姆（Prim）算法
    • 贪心算法
  • 最短路径