6.1 图的定义和基本术语

6.1.1 图的定义

图的示例

6.1.2 图的基本术语

用 $n$ 表示图中顶点数目，用 $e$ 表示边的数目。

  1. 子图：假设有两个图 $G=(V,E)$ 和 $G^{'}=(V^{'},E^{'})$ ，如果 $V^{'}\subseteq{V}$ 且 $E^{'}\subseteq{E}$ ，则称 $G^{'}$ 为 $G$ 的子图。

子图示例

  1. 无向完全图和有向完成图：

    1. 对于无向图，若具有 $n(n-1)/2$ 条边，则称为无向完全图。
    2. 对于有向图，若具有 $n(n-1)$ 条弧，则称为有向完全图。

  2. 稀疏图和稠密图：有很少条边或弧（如 $e\lt{n}\cdot{log_{2}{n}}$ ） 的图称为稀疏图，反之称为稠密图。

  3. 权和网：

    1. 在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权。
    2. 这些权可以表示从一个顶点到另一个顶点的距离或耗费。 这种带权的图通常称为网 。

  4. 邻接点：对于无向图 $G_1$ 如果图的边 $(v, v^{'})\in{E}$ ， 则称顶点 $v$ 和 $v^{'}$ 互为邻接点， 即 $v$ 和 $v^{'}$ 相邻接。边 $(v, v^{'})$ 依附于顶点 $v$ 和 $v^{'}$ ，或者说边 $(v,v^{'})$ 与顶点 $v$ 和 $v^{'}$ 相关联。

  5. 度、入度和出度：顶点的度是指和 $v$ 相关联的边的数目，对于有向图，顶点$v$的度分为入度和出度。入度是以顶点 $v$ 为头的弧的数目，出度是以顶点 $v$ 为尾的弧的数目

  6. 路径和路径长度：顶点 $v$ 到顶点 $w$ 之间的一条路径是指顶点序列。路径上边的数目称为路径长度。

  7. 回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。

  8. 简单路径、 简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一 个顶点和最后一个顶点之外 ， 其余顶点不重复出现的回路，称为简单回路或简单环 。

  9. 连通、连通图和连通分量：在无向图 $G$ 中，如果从顶点 $v$ 到顶点 $v'$ 有路径，则称 $v$ 和 $v'$ 是连通的。如果对千图中任意两个顶点 $v_i、v_j\in{V}$ ， $v_i$ 和 $v_j$ 都是连通的，则称 $G$ 是连通图。连通分量， 指的是无向图中的极大连通子图。

  10. 强连通图和强连通分量：在有向图 $G$ 中，如果对于每一对 $v_i,v_j\in{V}, v_i\neq{v_j}$ ，从 $v_i$ 到 $v_{j}$ 和 $v_j$ 到 $v_{i}$ 都存在路径，则称 $G$ 是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。例如图6.1. (a) 中的 $G_1$ 不是强连通图，但它有两个强连通分量，如图6.4 所示。

    G1的两个强连通分批

  11. 连通图的生成树：一个极小连通子图，它含有图中全部 顶点，但只有足以构成一 棵树的 $n-1$ 条边，这样的连通子图称为连通图的生成树。

    G3的最大连通分址的一棵生成树

  12. 有向树和生成森林：

    1. 有一个顶点的入度为0, 其余顶点的入度均为 1 的有向图称为有向树。

    2. 一 个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵 不相交的有向树的弧。

    3. 图 6.6 所示为其一例

    一个有向图及其生成森林

6.4图的存储结构

6.4.1 领接矩阵

邻接矩阵表示法

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。

例如，图 6.1 中所示的 $G_1$ 和 $G_2$ 的邻接矩阵如图 6.9所示。

图的示例

图的其邻接矩阵

$\infty$ 表示计算机允许的、 大于所有边上权值的数。例如， 图 6.10 所示 为一个有向网和它的邻接矩阵。

网及其邻接矩阵

邻接矩阵表示法的优缺点

优点
  1. 便于判断两个顶点之间是否有边， 即根据 $A[i][j] = 0$ 或 $1$ 来判断。
  2. 便于计算各个顶点的度。
缺点
  1. 不便于增加和删除顶点。
  2. 不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为 $O(n^2)$ 。
  3. 空间复杂度高。如果是有向图，$n$ 个顶点需要 $n^2$ 个单元存储边。如果是无向图，$n$ 个顶点需要 $n(n-1)/2$ 个单元存储边。但无论以何种方式存储，邻接矩阵表示法的空间复杂度均为 $O(n^2)$ ，这对于稀疏图而言尤其浪费空间。

6.4.2 邻接表

邻接表表示法

邻接表（Adjacency List）是图的一种链式存储结构。邻接表由两部分组成:表头结点表和边表。

  1. 表头结点表：由所有表头结点以顺序结构的形式存储， 以便可以随机访问任一顶点的边链表。表头结点包括数据域 (data) 和链域 (firstarc) 两部分， 如图6.11(a) 所示。
  2. 边表：由表示图中顶点间关系的 $2n$ 个边链表组成。 边链表中边结点包括邻接点域（adjvex）、数据域（info）和链域（nextarc）三部分，如图 6.11（b）所示。
  3. 表头结点和边结点

例如，图6.12 (a) 和 (b) 所示分别为图 6.1中 $G_1$ 和 $G_2$ 的邻接表。图 6.12 (c) 所示为有向图 $G_1$ 的 逆邻接表

图的示例

邻接表和逆邻接表

邻接表表示法的优缺点

优点
  1. 便千增加和删除顶点。
  2. 便千统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为 $O(n+e)$
  3. 空间效率高。对于一个具有 $n$ 个顶点 $e$ 条边的图 $G$ ， 若 $G$ 是无向图，则在其邻接表表示中有 $n$ 个顶点表结点和 $2e$ 个边表结点；若 $G$ 是有向图，则在它的邻接表表示或逆邻接表表示中 均有 $n$ 个顶点表结点和 $e$ 个边表结点。邻接表或逆邻接表表示的空间复杂度为 $O(n+e)$ ，适合表示稀疏图。 对于稠密图，考虑到邻接表中要附加链域，因此常采取邻接矩阵表示法。
缺点
  1. 不便于判断顶点之间是否有边，要判定 $v_i$ 和 $v_j$ 之间是否有边，就需扫描第 $i$ 个边表，最坏情况下要耗费 $O(n)$ 时间。
  2. 不便于计算有向图各个顶点的度。

6.4.3 十字链表

十字链表 (Orthogonal List) 是有向图的另一种链式存储结构。

在弧结点中有 5 个域:

  1. 尾域 (tailvex) ：弧尾这个顶点在图中的位置。
  2. 头域 (headvex) ：弧头这个顶点在图中的位置。
  3. 链域（hlink）指向弧头相同的下一条弧。
  4. 链域（tlink）指向弧尾相同的下一条弧。
  5. info 域指向该弧的相关信息。

顶点结点中由3个域组成

  1. data 域存储和顶点相关的信息，如顶点的名称等
  2. 链域（firstin）：指向以该顶点为弧头的第一个弧结点
  3. 链域（firstout）：指向以该顶点弧尾的第一个弧结点。

弧结点和顶点结点

例如，图6.14(a)中所示图的十字 链表如图6.14 (b)所示。

有向图的十字链表

6.4.4 邻接多重表

邻接多重表 (Adjacency Multilist) 是无向图的另一种链式存储结构

边结点

  1. 标志域（mark）：可用以标记该条边是否被搜索过；
  2. ivex 和 jvex 为该边依附的两个顶点在图中的位置；
  3. ilink指向下一条依附于顶点 ivex 的边；
  4. jlink 指向下一条依附于顶点jvex的边；
  5. info为指向和边相关的各种信息的指针域。

顶点结点

  1. data 域存储和该顶点相关的信息；
  2. firstedge域指示第一 条依附于该顶点的边。

边结点和顶点结点

图 6.16 所示为无向图 $G_2$ 的邻接多重表。

图的示例

无向图G2的邻接表

6.5 图的遍历

6.5.1 深度优先搜索

深度优先搜索（DepthFirst Search, DFS）遍历类似于树的先序遍历，是树的先序遍历的推广。

深度优先搜索

6.5.2 广度优先搜索

广度优先搜索（Breadth First Search, BFS）遍历类似于树的按层次遍历的过程。

广度优先搜索

6.6 图的应用

6.6.1 最小生成树

普里姆算法（最小连通）

普里姆算法

克鲁斯卡尔算法

克鲁斯卡尔算法

6.6.2 最短路径

迪杰斯特拉算法

迪杰斯特拉算法

6.6.3 拓扑排序

拓扑排序

6.6.4 关键路径

关键路径

关键路径：$v_1 \rightarrow v_3 \rightarrow v_4 \rightarrow v_6$

关键活动：$a_2, a_5, a_7$