图

1. 图的定义

表示“多对多”的关系

包含：

• 一组顶点：通常用 $V(Vertex)$ 表示顶点集合

• 一组边：通常用 $E(Edge)$ 表示边的集合

  • 边是顶点对： $(v, w) \in E$ ，其中 $v, w \in V$

  • 有向边 $<v, w>$ 表示从 $v$ 指向 $w$ 的边（单行线）

  • 不考虑重边和自回路

2. 抽象数据类型定义

• 类型名称：图 $(Graph)$

• 数据对象集合： $G(V, E)$ 由一个非空的有限顶点集合 $V$ 和一个有限边集合 $E$ 组成

• 操作集：对于任意图 $G \in Graph$ ，以及 $v \in V, e \in E$

  • Graph Create() ：建立并返回空图；

  • Graph InsertVertex(Graph G, Vertex v) ：将 $v$ 插入 $G$ ；

  • Graph InsertEdge(Graph G, Edge e) ：将 $e$ 插入 $G$ ；

  • void DFS(Graph G, Vertex v) ：从顶点 $v$ 出发深度优先遍历图 $G$ ；

  • void BFS(Graph G, Vertex v) ：从顶点 $v$ 出发宽度优先遍历图 $G$ ；

  • void ShortestPath(Graph G, Vertex v, int Dist[]) ：计算图 $G$ 中顶点 $v$ 到任意其它顶点的最短距离；

  • void MST(Graph G) ：计算图 $G$ 的最小生成树；

  • $\cdots \cdots$

3. 图的表示

3.1 邻接矩阵

邻接矩阵 $G[N][N]$ ： $N$ 个顶点从 0 到 N-1 编号

$G[i][j]=\left\{ \begin{aligned} 1 ， &若 <v_i, v_j> 是 G 中的边 \\ 0 ， &否则 \end{aligned} \right.$

对于无向图的存储，省一半空间的方法

优点：

• 直观、简单、好理解

• 方便检查任意一对顶点间是否存在边

• 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

• 方便计算任一顶点的“度”（从该点出发的边数为“出度”，指向该点的边数为“入度”）

  • 无向图：对应行（或列）非0元素的个数

  • 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”

缺点：

• 浪费空间

  • 稀疏图（点很多而边很少）有大量无效元素

  • 稠密图（特别是完全图）还是很合算的

• 浪费时间：统计稀疏图中一共有多少边

3.2 邻接表

邻接表： $G[N]$ 为指针数组，对应矩阵每行一个链表，只存非0元素

一定要足够稀疏才合算

优点：

• 方便找任一顶点的所有“邻接点”

• 节约稀疏图的空间

  • 需要 N 个头指针 + 2E 个结点（每个结点至少 2 个域）

• 方便计算任一顶点的“度”？

  • 对于无向图：是的

  • 对于有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来计算“入度”

缺点：

• 不方便计算任意一对顶点间是否存在边

4. 图的一些概念

• 连通：如果从 $V$ 到 $W$ 存在一条 （无向）路径，则称 $V$ 和 $W$ 是连通的
• 路径： $V$ 到 $W$ 的路径是一系列顶点 $\{ V, v_1, v_2, \cdots , v_n, W \}$ 的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果 $V$ 到 $W$ 之间的所有顶点都不同，则称简单路径
• 回路：起点等于终点的路径

• 连通图：图中任意两顶点均连通

• 连通分量：无向图的极大连通子图

  • 极大顶点数：再加1个顶点就不连通

  • 极大边数：包含子图中所有顶点相连的所有边

• 强连通：有向图中顶点 $V$ 和 $W$ 之间存在双向路径，则称 $V$ 和 $W$ 是强连通的
• 强连通图：有向图中任意两顶点均强连通

• 强连通分量：有向图的极大强连通子图