数据结构-第6章—图

图

2025/4/13

图的基本概念

定义

• 图不能是空图，V非空，E可以为空。

• 有向图：

• 无向图: (a,b)

完全图

• 有向完全图：n(n-1)
• 无向完全图：$\frac {n*(n-1)}{2}$

连通性（有向图） ，强连通性（无向图）

• （强）连通分量——极大（强）连通子图——尽可能包含更多的点和边

生成树

• 最小生成树——极小连通子图——包含必要的n-1条边
• 若边权相同 ，最小生成树不唯一

度

• 无向图：V = 2*m
• 有向图：$V_{in} = V_{out} = m$

环

• n ,m>n-1

简单路径，回路

• 只经过一次

有向树

• 一个入度为0的点，其余全为入度为1的点

图的存储

• 邻接表

  • 空间复杂度 O(n+e) O(n+_2e)
  • 入度遍历所有节点
  • 不唯一

• 邻接矩阵

  • 二维数组
  • 空间复杂度$O(n^3)$
  • 压缩存储
  • $A^n$长度为n的路径数
  • 对角线以上（下）全为0，不存在环
  • 唯一

• 十字链表法

• 邻接多重表

图的遍历

• BFS 层次遍历

  • 非带权图的单源最短路

• DFS 后根遍历

• 空间复杂度O(V)，

• 时间复杂度

  • 邻接表 $O(V^2)$
  • 邻接矩阵 $O(V+E)$

• 广度优先生成树和深度优先生成树

  • 邻接矩阵 唯一
  • 邻接表 不唯一