跳到主要内容

图

图 是由顶点集和边集组成，记为 G=(V,E)G = (V, E) 。其中，VV 不得为空。

用 ∣V∣|V| 表示顶点数，也称图的 阶 ；用 ∣E∣|E| 表示边数。

若一个图没有重复边和自环的图，则称为 简单图 ，否则称为 多重图 。

自环：一条连接一个顶点和其自身的边。

路径：从顶点 vv 到顶点 ww 的路径是一个顶点序列。

回路：第一个顶点和最后一个顶点相同的路径，也称 环 。

简单路径：路径序列中顶点各不相同的路径。

简单回路：除第一和最后一个顶点，其余顶点各不相同的回路。

路径长度：路径中边的数目。

点到点的距离：两点之间的最短路径长度。若不存在路径，则为无穷大。

若有两个图 G=(V,E)G = (V, E) 和 G′=(V′,E′)G' = (V', E') ，且 V′⊆VV' \subseteq V 且 E′⊆EE' \subseteq E ，则称 G′G' 是 GG 的 子图 。若又有 V′=VV' = V ，则称 G′G' 是 GG 的 生成子图 。

在一个图中，每条边都有一个与之相关的数值，称为 边的权 。这类图也称为 带权图 ，也称 网 。

带权路径长度：路径上各边的权值之和。

无向图及有向图​

图可分 有向图 和 无向图 ，取决于边是否有方向。

无向图​

无向边（简称 边 ）记为 (v,w)(v, w) ，其中 vv 和 ww 称为 顶点对 。(v,w)(v, w) 和 (w,v)(w, v) 是同一条无向边。

顶点的度：与顶点相关联的边的数目，记为 TD(v)TD(v) 。

顶点的度 = 2 * 边数。

若两点间有路径存在，则称这两点是 连通 的。若图中任意两点都是连通的，则称该图是 连通图 。

一个无向图若不存在回路，且为连通图，则可视为树。

无向图中的极大连通子图称为 连通分量 。

连通图的 生成树 是一个极小连通子图，它含有图中全部 nn 个顶点，但只有足以构成一棵树的 n−1n - 1 条边。

无向完全图：任意两个顶点之间都存在边的无向图。

有向图​

有向边（简称 弧 ）记为 <v,w><v, w> ，其中 vv 称为 弧尾 ，ww 称为 弧头 。<v,w><v, w> 和 <w,v><w, v> 是两条不同的有向边。

顶点的度分为 入度 和 出度 ：

  • 入度：以 vv 为终点的有向边的数目，记为 ID(v)ID(v) 。
  • 出度：以 vv 为起点的有向边的数目, 记为 OD(v)OD(v) 。

入度 = 出度 = 边数。

有向树：一个顶点的入度为 0，其余顶点的入度为 1 的有向图。

若两点间两方向均存在路径，则称这两点是 强连通 的。若图中任意两点都是强连通的，则称该图是 强连通图 。

若 G 是强连通图，则最少有 nn 条边（形成回路）。

有向图中的极大强连通子图称为 强连通分量 。

有向完全图：任意两个顶点之间都存在方向相反的两条弧的有向图。

图的存储​

邻接矩阵​

用一个二维数组来表示图。其中，二维数组的行和列均代表顶点，数组元素的值表示顶点之间的关系。

#define MAX_VERTEX_NUM 100

typedef struct {
    Element vertex[MAX_VERTEX_NUM];
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexNum, edgeNum;
} MGraph;

若用邻接矩阵表示带权图，则可以用数组元素的值表示权值。

空间复杂度为 O(n2)O(n^2) ，适合存储稠密图。

设 G 的邻接矩阵为 AA（矩阵元素为 0 或 1），则 AkA^k 中的元素 An[i][j]A^n[i][j] 表示从顶点 ii 到顶点 jj 的长度为 kk 的路径数目。

邻接表​

用一个数组存储顶点信息，对于每个顶点，用链表存储其邻接点信息。

typedef struct VNode {
    Element data;
    ArcNode *first;
} VNode, AdjList[MAX_VERTEX_NUM];

缺点：

  • 对于无向图，每条边都要存储两次，浪费空间。
  • 对于有向图，求顶点的入度需要遍历整个邻接表，效率低。

十字链表​

十字链表只适用于存储有向图。

用一个数组存储顶点信息，对于每个顶点，用两个链表分别存储其入度和出度的邻接点信息。

// 顶点结点
typedef struct VNode {
    Element data;
    ArcNode *firstIn, *firstOut;
} VNode, AdjList[MAX_VERTEX_NUM];

// 弧结点
typedef struct ArcNode {
    int tailVex, headVex;   // 弧尾、弧头对应顶点编号
    ArcNode *nextIn;    // 下一个入度弧
    ArcNode *nextOut;   // 下一个出度弧
    InfoType info;      // 权值
} ArcNode;

优点：

  • 空间复杂度为 O(∣V∣+∣E∣)O(|V| + |E|) ，适合存储稀疏图。
  • 求顶点的入度和出度只需沿着 firstIn 或 firstOut 指针遍历即可。

邻接多重表​

邻接多重表只适用于存储无向图。

用一个数组存储顶点信息，对于每个顶点，用两个方向的链表分别存储其邻接点信息。

// 顶点结点
typedef struct VNode {
    Element data;
    EdgeNode *firstEdge;
} VNode, AdjList[MAX_VERTEX_NUM];

// 边结点
typedef struct EdgeNode {
    int iVex, jVex; // 该边依附的两个顶点
    EdgeNode *iNext, *jNext;    // 分别指向依附这两个顶点的下一条边
    InfoType info;  // 权值
} EdgeNode;

图的操作​

不同的存储结构对应的操作的时间复杂度不同。

  • 查询边
  • 查询邻接顶点 x 的边
  • 插入、删除顶点
  • 插入、删除边

图的遍历​

广度优先遍历​

  • 需要一个辅助队列记录需要遍历的结点。
  • 需要一个辅助数组 visited ，记录顶点是否被访问过。

时间复杂度：

  • 邻接矩阵：O(∣V∣2)O(|V|^2)
  • 邻接表：O(∣V∣+∣E∣)O(|V| + |E|)

通过 BFS 可以生成一棵树（或森林），称为 广度优先生成树 。

深度优先遍历​

递归搜索。

空间复杂度：来自函数调用栈，最坏情况下为 O(∣V∣)O(|V|) 。

时间复杂度：与 BFS 相同。

最小生成树​

对于一个带权连通无向图，其生成树的权值之和最小的生成树称为 最小生成树（MST）。

同一个图可能有多钟不同的最小生成树。

只有连通图才有生成树，非连通图只有生成森林。

Prim 算法​

  1. 从图中任意选取一个顶点作为起点，开始构建生成树；
  2. 从与生成树相邻的顶点中选取权值最小的边，将其加入生成树；
  3. 重复步骤 2，直到生成树中包含 n−1n - 1 条边。

适用于边稠密图，时间复杂度为 O(∣V∣2)O(|V|^2) 。

Kruskal 算法​

  1. 将图中的所有边按照权值从小到大排序；
  2. 从权值最小的边开始，若当前边的两顶点不连通（并查集），则将其加入生成树；
  3. 重复步骤 2，直到生成树中包含 n−1n - 1 条边。

适用于边稀疏图，时间复杂度为 O(∣E∣log⁡∣E∣)O(|E| \log |E|) 。

最短路径问题​

无权图的最短路径​

对于无权图，直接用 BFS 即可。

Dijkstra 算法​

Dijkstra 算法不能处理带负权值的图，即在探索过程中，要求权值只增不减。

需先准备三个数组：

bool checked[VERTEX_NUM]; // 记录各顶点是否已被确定下来，初始化为 false
int dist[VERTEX_NUM]; // 记录源点到各顶点的最短路径长度，初始化为无穷大
int path[VERTEX_NUM]; // 记录各顶点在最短路径上的前一个结点，初始化为 -1

算法的时间复杂度为 O(∣V∣2)O(|V|^2) ，步骤如下：

  1. 对源点进行初始化：
    • 将其对应的 checked 置为 true ；
    • 将其对应的 dist 置为 0 ；
    • 对其所有邻接点，将其对应的 dist 置为对应边的权值，将其对应的 path 置为源点编号。
  2. 遍历 dist 数组，找到其中最小的值，对应的顶点编号记为 ii ；
    • 将 ii 对应的 checked 置为 true ；
    • 对 ii 的所有邻接点 jj ，若 dist[i] + edge[i][j] < dist[j] ，则更新 dist[j] 和 path[j] 。
  3. 重复步骤 1 ，直到 checked 数组中所有元素均为 true 。

Floyd 算法​

Floyd 算法可以处理带负权值的图，但不能处理带负权回路的图。

Floyd 算法属于动态规划，它以“中转点”为动态条件，逐步地更新各顶点之间的最短路径长度。

算法的时间复杂度为 O(∣V∣3)O(|V|^3) ，实现代码如下：

int dist[VERTEX_NUM][VERTEX_NUM];   // 记录各顶点之间的最短路径长度
int path[VERTEX_NUM][VERTEX_NUM];   // 记录各顶点之间的最短路径上的中转点

for (int k = 0; k < n; k += 1) {    // 中转点
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < n; j += 1) {
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
                path[i][j] = k;
            }
        }
    }
}

和 Dijkstra 一致，需要以回溯的方式根据 path 数组找到最短路径：

void printPath(int i, int j) {
    if (path[i][j] == -1) { // 不存在中转点
        cout << i << " -> " << j << endl;
    } else {
        printPath(i, path[i][j]);
        printPath(path[i][j], j);
    }
}

拓扑排序​

AOV 网​

AOV 网：Activity On Vertex Network，即顶点表示活动的有向图。

可以用有向无环图（DAG）表示一个工程。其中，顶点表示活动，边表示活动之间的优先关系。

拓扑排序​

对 AOV 网进行拓扑排序，即将所有顶点排成一个序列，使得所有的有向边均从序列的前面指向后面。

实现步骤：

  1. 从 AOV 网中选择一个入度为 0 的顶点，输出之；
  2. 从 AOV 网中删除该顶点及其所有出边；
  3. 重复步骤 1 和 2 ，直到 AOV 网为空。

每个 AOV 网都有一个或多个拓扑序列，但是如果 AOV 网中有环，则不存在拓扑序列。

逆拓扑排序​

与拓扑排序相反，逆拓扑排序考虑的是出度为 0 的顶点。

实现方法可以用与拓扑排序类似的方法，也可以使用 DFS（先遍历后输出）。

关键路径​

AOE 网​

AOE 网：Activity On Edge Network，即边表示活动的有向图。在 AOE 网中：

  • 顶点表示事件，边表示活动，边上的权值表示活动的持续时间；
  • 仅有一个入度为 0 的顶点，称为 源点 ，表示工程的开始；
  • 仅有一个出度为 0 的顶点，称为 汇点 ，表示工程的结束。

关键路径​

从源点到汇点的最长路径称为 关键路径 。关键路径上的活动称为 关键活动 。

活动 aia_i 的时间余量为最早开始时间与最晚开始时间之差，即 li−eil_i - e_i 。

实现方法：

  1. 对 AOE 网进行拓扑排序，得到拓扑序列；
  2. 从源点开始，依次计算各顶点的最早开始时间 eie_i ；
  3. 从汇点开始，依次计算各顶点的最晚开始时间 lil_i ；
  4. 依次计算各活动的时间余量 li−eil_i - e_i ，若为 0 ，则该活动为关键活动。

若关键活动耗时增加，则关键路径长度增加；