图

在数据结构的学习中，我们已经掌握了数组、链表等线性结构，以及树这样的层次结构。然而，许多实际问题中的关系无法用简单的线性或层次关系表示，需要更复杂的网络结构来描述实体之间的多对多关系。

图（Graph） 是一种重要的非线性数据结构，用于表示具有复杂关系的数据集合。图结构在计算机科学中应用广泛，包括社交网络分析、路由算法、依赖关系管理、编译器设计等领域。 从社交网络中的用户关系、城市交通图中的道路连接，到互联网中的网页链接，图无处不在，它能够精确地模拟现实世界中任何复杂的多对多关系。

图的定义与基本概念

形式化定义

设 $G = (V, E)$ 是一个图，其中 $V$ 是顶点的有限集合，$E \subseteq V \times V$ 是边的集合。对于无向图，边是无序对 $(u, v)$，表示顶点 $u$ 和 $v$ 之间存在连接关系。对于有向图，边是有序对 $(u, v)$，表示从顶点 $u$ 指向顶点 $v$ 的有向连接。

图 $G = (V, E)$ 的基本要素包括：

• 顶点（Vertex），也称为节点（Node），是图中的基本实体，用 $v \in V$ 表示。在社交网络中，每个用户是一个顶点；在城市地图中，每个路口或地点是一个顶点；在网页链接图中，每个网页是一个顶点。
• 边（Edge），也称为弧（Arc），是连接两个顶点的关系，用 $e = (u, v) \in E$ 表示。对于无向图，边 $(u, v)$ 等价于边 $$；对于有向图，边 表示从 到 的有向连接，与边 是不同的。

图的分类

根据边的性质和权重的存在性，图可以分为不同的类型，每种类型适用于不同的应用场景。

• 无向图（Undirected Graph）：图中的边是无序的，即边 $(u, v)$ 等价于边 $(v, u)$。无向图适用于表示对称关系，如社交网络中的好友关系、城市地图中的双向道路。在无向图中，如果存在边 $(u, v)$，则称顶点 $u$ 和 $v$ 是相邻（Adjacent） 的，边 与顶点 和 。

理解了图的这些基本分类，我们就能开始思考如何在计算机程序中高效地表示和操作这些复杂的网络结构。

图的表示方法

要在程序中表示一张图，我们主要有两种经典的方法：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。选择哪一种表示方法，取决于图的密度（边的数量相对于顶点的数量）、需要频繁执行的操作类型，以及可用的存储空间。

邻接矩阵

邻接矩阵（Adjacency Matrix） 是一种直观的图表示方法。对于包含 $|V|$ 个顶点的图 $G = (V, E)$，我们创建一个 $|V| \times |V|$ 的二维矩阵 $A$，其中矩阵元素 $$ 表示顶点 和顶点 之间的关系。

对于无权图，如果存在边 $(i, j)$，则 $A[i][j] = 1$，否则 $A[i][j] = 0$。对于有向图，$A[i][j$ 表示存在从顶点 指向顶点 的边，而 可能为 （除非也存在反向边）。对于无向图，由于边是无序的，邻接矩阵是对称的，即 。

对于加权图，$A[i][j]$ 存储边 $(i, j)$ 的权重值。如果边不存在，通常用 $\infty$ 或一个特殊值（如 $-1$）表示。

空间复杂度：邻接矩阵的空间复杂度为 $O(|V|^2)$，无论图中实际存在多少条边。对于包含 $n$ 个顶点的图，需要存储 $n^2$ 个矩阵元素。

时间复杂度分析：

• 查询操作：判断顶点 $i$ 和 $j$ 之间是否存在边，时间复杂度为 $O(1)$，因为只需要访问矩阵元素 $A[i][j]$。这是邻接矩阵的主要优势。
• 遍历邻接顶点：获取顶点 $i$ 的所有邻接顶点，需要遍历矩阵的第 $i$ 行（或第 列），时间复杂度为 ，即使顶点 的实际邻接顶点数量很少。

|
#include <iostream>
#include <vector>
 
// 使用邻接矩阵表示一个简单的无向无权图
class GraphMatrix {
private:
    // adjMatrix 是一个二维向量，用来存储邻接矩阵
    std::vector<std::vector<int>> adjMatrix;
    // numVertices 存储顶点的数量
    int numVertices;
 
public:
    // 构造函数，初始化一个有 V 个顶点的图
    GraphMatrix(int V) {
        numVertices = V;
        // 将二维向量的大小调整为 V x V，并用0填充
        adjMatrix.resize(V, 

邻接表

邻接表（Adjacency List） 是针对邻接矩阵空间浪费问题的有效解决方案。邻接表为每个顶点维护一个列表，该列表只存储与该顶点相邻的顶点，而不是存储所有可能的顶点对。

具体来说，我们创建一个大小为 $|V|$ 的数组，数组的每个位置 $i$ 对应图中的顶点 $i$。在这个位置上，我们存储一个动态数据结构（如链表或向量），该结构中只包含顶点 $i$ 的所有邻接顶点。对于有向图，邻接表通常只存储出边（从该顶点出发的边）；对于无向图，需要在两个顶点的邻接表中都添加对方。

空间复杂度：邻接表的空间复杂度为 $O(|V| + |E|)$。对于包含 $n$ 个顶点和 $m$ 条边的图，需要存储 $n$ 个列表头指针，以及 $m$ 条边的信息（对于无向图，每条边存储两次；对于有向图，每条边存储一次）。对于稀疏图（$\mathrm{\mid }E\mathrm{\mid }\ll \mathrm{\mid }$），邻接表的空间效率远高于邻接矩阵。

时间复杂度分析：

• 查询操作：判断顶点 $i$ 和 $j$ 之间是否存在边，需要遍历顶点 $i$ 的邻接表，时间复杂度为 $O(\text{deg}(i))$，其中 $\text{deg}(i)$ 是顶点 $i$ 的度。最坏情况下，如果顶点 与所有其他顶点都相邻，时间复杂度为 。

在实际应用中，大多数图都是稀疏图（边的数量远小于 $|V|^2$），因此邻接表是实际应用中最常用、最高效的图表示方法。大多数图算法库和数据结构实现都采用邻接表作为默认的图表示方法。

|
#include <iostream>
#include <vector>
#include <list>
 
// 使用邻接表表示一个简单的无向无权图
class GraphList {
private:
    // adjList 是一个向量，每个元素是一个存储整数的链表
    // 数组的索引代表顶点，链表中的元素代表该顶点的邻接顶点
    std::vector<std::list<int>> adjList;
    // numVertices 存储顶点的数量
    int numVertices;
 
public:
    // 构造函数，初始化一个有 V 个顶点的图
    GraphList(int V) {
        numVertices = V;
        // 将向量的大小调整为 V，每个位置都是一个空的链表

图的遍历算法

图的遍历是指系统性地访问图中的每一个顶点，确保每个顶点被访问且仅被访问一次的过程。遍历算法是图算法的基础，许多复杂的图算法都建立在遍历算法之上。

最经典、最重要的两种遍历策略是广度优先搜索（BFS）和深度优先搜索（DFS）。这两种算法采用不同的访问策略，适用于不同的应用场景。

广度优先搜索 (BFS)

**广度优先搜索（Breadth-First Search, BFS）**采用层次遍历的策略，从起始顶点开始，先访问距离起始顶点最近的顶点（第一层），然后访问距离起始顶点次近的顶点（第二层），以此类推，逐层向外扩展。

为了实现这种层次访问顺序，BFS 使用**队列（Queue）**这种先进先出（FIFO）的数据结构来维护待访问的顶点序列。

算法描述：

设图 $G = (V, E)$，起始顶点为 $s \in V$。BFS 算法的伪代码描述如下：

|
BFS(G, s):
    初始化 visited 数组，标记所有顶点为未访问
    创建队列 Q
    visited[s] = true
    Q.enqueue(s)
    
    while Q 不为空:
        u = Q.dequeue()
        访问顶点 u
        
        for each 顶点 v in adjList[u]:  // 遍历 u 的所有邻接顶点
            if visited[v] == false:
                visited[v] = true
                Q.enqueue(v)

算法正确性：BFS 算法能够访问从起始顶点 $s$ 可达的所有顶点，且每个顶点仅被访问一次。使用归纳法可以证明：在第 $k$ 次迭代时，队列中包含的是距离起始顶点 $s$ 恰好为 $k$ 的所有顶点，且这些顶点按照入队顺序被访问。

时间复杂度分析：对于包含 $|V|$ 个顶点和 $|E|$ 条边的图，BFS 的时间复杂度为 $O(|V| + |E|)$。每个顶点被访问一次（入队和出队各一次），每条边被检查一次（在遍历邻接表时）。对于使用邻接表表示的图，这是最优的时间复杂度。

空间复杂度分析：BFS 的空间复杂度为 $O(|V|)$。visited 数组需要 $O(|V|)$ 空间，队列在最坏情况下可能包含 $O(|V|)$ 个顶点（例如，当起始顶点与所有其他顶点都相邻时）。

重要应用：BFS 的一个重要应用是在无权图中寻找最短路径。由于 BFS 按照距离起始顶点的远近逐层访问，它找到的从起始顶点到目标顶点的第一条路径，必然是经过边数最少的最短路径。这个性质使得 BFS 成为解决无权图最短路径问题的标准算法。

|
#include <iostream>
#include <vector>
#include <list>
#include <queue>
 
class Graph {
private:
    int numVertices;
    std::vector<std::list<int>> adjList;
 
public:
    Graph(int V) : numVertices(V) {
        adjList.resize(V);
    }
 
    void addEdge(int

深度优先搜索 (DFS)

深度优先搜索（Depth-First Search, DFS） 采用深度优先的策略，从起始顶点开始，选择一条路径尽可能深地探索，直到无法继续前进（到达没有未访问邻接顶点的顶点），然后回溯到上一个顶点，选择另一条路径继续探索。

DFS 可以使用递归实现，也可以使用显式栈实现。递归实现简洁直观，直接反映了 DFS 的递归性质；显式栈实现避免了递归调用的函数调用开销，在某些情况下性能更好。

算法描述：

设图 $G = (V, E)$，起始顶点为 $s \in V$。DFS 算法的递归实现伪代码描述如下：

|
DFS(G, s):
    初始化 visited 数组，标记所有顶点为未访问
    DFS_Visit(G, s, visited)
 
DFS_Visit(G, u, visited):
    visited[u] = true
    访问顶点 u
    
    for each 顶点 v in adjList[u]:  // 遍历 u 的所有邻接顶点
        if visited[v] == false:
            DFS_Visit(G, v, visited)  // 递归访问未访问的邻接顶点

算法正确性：DFS 算法能够访问从起始顶点 $s$ 可达的所有顶点，且每个顶点仅被访问一次。使用归纳法可以证明：对于任意从 $s$ 可达的顶点 $v$，DFS 算法最终会访问 $v$，且访问过程不会重复。

时间复杂度分析：对于包含 $|V|$ 个顶点和 $|E|$ 条边的图，DFS 的时间复杂度为 $O(|V| + |E|)$。每个顶点被访问一次，每条边被检查一次。对于使用邻接表表示的图，这是最优的时间复杂度。

空间复杂度分析：DFS 的空间复杂度取决于实现方式。对于递归实现，空间复杂度为 $O(|V|)$，主要由递归调用栈的深度决定。最坏情况下，如果图退化为一条链，递归深度为 $|V|$，空间复杂度为 $O(|V|)$。对于显式栈实现，空间复杂度同样为 $O(|V|)$。

重要应用：DFS 在图算法中应用广泛，包括检测图中是否存在环路、进行拓扑排序（确定有向无环图中顶点的线性顺序）、寻找连通分量（找出图中所有相互连通的顶点集合）、强连通分量分解（找出有向图中所有强连通的子图）等。

|
#include <iostream>
#include <vector>
#include <list>
 
class GraphDFS {
private:
    int numVertices;
    std::vector<std::list<int>> adjList;
 
    // DFS 的辅助递归函数
    // 时间复杂度: O(|V| + |E|)，空间复杂度: O(|V|)
    void DFSUtil(int u, std::vector<bool>& visited) {
        // 标记当前顶点为已访问并访问它

小练习

4. 图的表示方法复杂度分析练习

设图 G = (V, E) 包含 n 个顶点和 m 条边。请分析以下问题：

• 使用邻接矩阵表示图 G 时，空间复杂度是多少？如果 m << n²（稀疏图），这种表示方法的主要缺点是什么？
• 使用邻接表表示图 G 时，空间复杂度是多少？对于稀疏图，为什么邻接表比邻接矩阵更高效？
• 在无权图中，为什么 BFS 能够找到从起始顶点到目标顶点的最短路径？

|
#include <iostream>
using namespace std;
 
int main()
{
    cout << "=== 图的表示方法复杂度分析 ===" << endl << endl;
 
    cout << "1. 邻接矩阵：" << endl;
    cout << "   - 空间复杂度: O(n²)" << endl;
    cout << "   - 原因: 使用 n×n 的二维数组存储所有可能的边" << endl;
    cout << "   - 稀疏图的缺点:" << endl;
    cout 

5. 图的遍历模拟练习

给定以下有向图，顶点编号为 0 到 5（A=0, B=1, C=2, D=3, E=4, F=5）：

• A -> B, A -> C
• B -> D, B -> E
• C -> E
• D -> F
• E -> F

要求：

1. 手动模拟从顶点 0（A）开始的 BFS 遍历，写出访问顶点的顺序
2. 手动模拟从顶点 0（A）开始的 DFS 遍历，写出访问顶点的顺序

|
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
using namespace std;
 
// 辅助函数：打印整数向量
string vectorToString(const vector<int>& vec)
{
    if (vec.empty()) return "[]";
    stringstream ss;
    ss << "[";
    for

6. 检测有向图中的环路练习

实现一个 HasCycle() 方法，用于检测一个有向图中是否存在环路。

要求：使用 DFS 实现，在 DFS 遍历时，除了 visited 数组，还需要一个 recursionStack 数组来跟踪当前递归路径上的顶点。如果访问到一个已经在当前递归路径中的顶点，则说明存在环路。

|
#include <iostream>
#include <vector>
using namespace std;
 
class Graph
{
private:
    int vertices;
    vector<vector<int>> adjList;
 
public:
    Graph(int v) : vertices(v)
    {
        adjList.resize(v);
    }
 
    void addEdge(int

缺点：

• 查询效率较低：判断两个顶点之间是否存在边，需要遍历其中一个顶点的邻接表，时间复杂度为 $O(\text{deg}(i))$，最坏情况下为 $O(|V|)$。
• 实现相对复杂：需要使用动态数据结构（链表或向量），代码实现比邻接矩阵稍复杂。

说明：

• 邻接矩阵：
  • 空间复杂度：O(n²)
  • 优点：查询边是否存在 O(1)
  • 缺点：对于稀疏图浪费空间
• 邻接表：
  • 空间复杂度：O(n + m)
  • 优点：只存储实际存在的边，空间效率高
  • 缺点：查询边是否存在需要 O(度)
• BFS 找最短路径：
  • BFS 按层遍历，保证第一次访问某个顶点时路径最短
  • 在无权图中，BFS 能找到最短路径
  • 时间复杂度：O(n + m)

说明：

• BFS 遍历顺序：0, 1, 2, 3, 4, 5（A, B, C, D, E, F）
  • 按层遍历，先访问距离起点近的顶点
  • 使用队列实现，保证先入队的先访问
• DFS 遍历顺序：0, 1, 3, 5, 4, 2（A, B, D, F, E, C）
  • 深度优先，尽可能深入再回溯
  • 使用递归实现，递归调用栈模拟遍历过程
• 关键区别：
  • BFS：按层遍历，适合找最短路径
  • DFS：深度优先，适合遍历所有路径

说明：

• 算法思路：
  • 使用 DFS 遍历图
  • visited 数组标记已访问的顶点
  • recursionStack 数组跟踪当前递归路径上的顶点
  • 如果访问到一个已经在 recursionStack 中的顶点，说明存在环路
• 关键点：
  • 回溯时需要将顶点从 recursionStack 中移除
  • 只有当前递归路径中的顶点才算环路，已访问但不在当前路径中的不算
• 时间复杂度：O(V + E)，需要遍历所有顶点和边
• 空间复杂度：O(V)，需要 visited 和 recursionStack 数组，递归调用栈深度为 O(V)
• 与遍历算法的比较：
  • 时间复杂度相同：O(V + E)
  • 空间复杂度相同：O(V)
  • 但需要额外的 recursionStack 数组来跟踪当前路径