数据结构_6图

参考王道计算机考研《数据结构》，自主进行知识点归纳总结，必备复习资料分享，方便大家备考时翻阅查看，提高复习效率，希望对大家备考有所帮助。

图

• 常考点
  • 图的基本概念常考点
    • 
  • 每个顶点的度：以该顶点为一个端点的边的数目（有向OR无向）
    • 无论有向图还是无向图，各个顶点度的求和 = 2|E|
• 基本概念
  • 定义
    • G={V,E}（V：顶点的有限非空集；E：边集(必须连接两顶点)）
    • 注意
      • 顶点的个数称为图的阶
      • 图不可以空（V一定是非空集，E可以是空集）
  • 有向图
    • 定义
      • 有向边(弧)是顶点的有序对(<A,B>≠<B,A>)
        • 弧头：弧——有箭头的一端 弧尾：弧——无箭头的一端 弧尾邻接到弧头 弧头邻接自弧尾
    • 顶点的度
      • TD(v) = ID(v)+OD(v)
        • ID(v):以顶点v为终点的有向边的数目（众矢之的）
        • OD(v):以顶点v为起点的有向边的数目（发射地）
      • 有向图的全部顶点的出度和=入度和=边数|E|
        •  每条边为其连接的两个顶点各贡献一个入度和一个出度
    • 强连通图
      • 若图中任何一对顶点都是强连通的
        • 强连通：顶点间正向路径和逆向路径均存在 
      • n个顶点——最少有n条边（形成回路）
        •  其中任一结点都能与其余任一结点进行连通
  • 无向图
    • 定义
      • 无向边是顶点的无序对((A,B)=(B,A))
    • 顶点的度
      • 指依附于该顶点的边的条数，记为TD(v)
      • 无向图的全部顶点的度的和等于边数的2倍
        •  每一条边为其连接的两顶点各贡献一个度——无向图中每一条边为整个图贡献两个度
    • 连通图
      • 连通：顶点到顶点有路径存在
      • n个顶点（连通图）——最少有n-1条边
        • 
      • n个顶点（非连通图）——最多有(n-1)(n-2)/2条边
        • 有一个顶点被孤立出来（非连通图），其余各个顶点两两连通(使边数尽可能多) 
  • 边的权、带权图（网）
    • 
  • 点与点关系
    • 
    • 路径长度
      • 路径上边的数目
    • 简单路径（顶点不重复出现）、简单回路（中间顶点不重复出现）
    • 点到点的距离
      • 
      • 路径存在——最短路径的长度
      • 路径不存在——距离为∞
  • 图与图关系
    • 子图（边集是原图边集的子集，顶点集是原图顶点集的子集）
      • 
    • 生成子图（边集是原图边集的子集，顶点集是原图顶点集的全体）
    • 连通分量
      • 无向图中的极大连通子图
        • 子图必须连通，且包含尽可能多的顶点和边 
    • 强连通分量
      • 有向图中的极大强连通子图
        • 子图必须强连通，且包含尽可能多的顶点和边 
    • 连通图的生成树(不唯一)
      • 
      • 包含图中全部顶点的一个极小连通子图
        • 边尽可能的少，但要保持连通（图中顶点数为n，则它的生成树含有n-1条边）
    • 非连通图的生成森林
      •  图中只是G的连通分量，若构成G的生成森林，还需要将G的连通分量转换成对应的生成树 
      • 在非连通图中，①连通分量的②生成树构成
  • 几种特殊形态的图
    • 有向图
      • 有向树
        • 一个顶点的入度为0、其余顶点的入度均为1的有向图
          • 
      • 有向完全图
        • 
        • 有向图中任意两个顶点之间都存在方向相反的两条弧
          • 
    • 无向图
      • 树
        • 不存在回路，且连通的无向图
          • 
      • 无向完全图
        • 
        • 无向图中任意两个顶点之间都存在一条边
          • 
    • 稀疏图
      • 边数很少的图
    • 稠密图
      • 边数很多的图
    • 无绝对界限
      • 
• 存储结构
  • 
  • 邻接矩阵法
    •  （1）（2）：找入边出边和求入度出度方法一致  （3） 
  • 邻接表法
    • 
    • 顺序（存储顶点）+链式存储（边/弧表）
      • 邻接表法存储的图
        • 
      • “顶点”
        •  【注】AdjList为结构数组
      • “弧”/“边”
        •  【注】adjvex：当前邻接到的结点（当前弧/边指向的结点）
    • 无向图
      • 
      • 每个结点指向第一条边（冗余）
      • 空间复杂度O(|V|+2|E|)
    • 有向图
      • 
      • 每个结点指向弧(出边-无冗余)
      • 空间复杂度O(|V|+|E|)
      • 找入边很麻烦(O|E|)
    • 每个顶点指向的边表最多只有|V|(最多连接|V|-1个顶点)
  • 邻接多重表（只存储无向图）
    • 顶点结点(一个指针域)、弧结点
      • 
    • 空间复杂度O(|V|+|E|)(每条边只对应一份数据)
  • 十字链表（只存储有向图）
    • 顶点结点、弧结点
      • 
    • 性能分析
      • 
      • 指定顶点的所有出边
        • 顺着绿色线路照(弧尾顶点编号相同)
      • 指定顶点的所有入边
        • 顺着红色线路照(弧头顶点编号相同)
      • 空间复杂度O(|V|+|E|)