第59章 图的定义及基本图论算法
搜索知识点 /

第59章 图的定义及基本图论算法

图（Graph）是一种比线性表和树更复杂的非线性数据结构，由**顶点（Vertex）和边（Edge）**组成，能够描述多对多的复杂关系，在社交网络、路线规划、电路设计、图像处理和迷宫求解等领域都有广泛应用。

本章先建立图的基本概念（定义、种类、度、存储结构），再讲解两种最基础的图遍历算法——深度优先搜索（DFS）与广度优先搜索（BFS），最后重点展开泛洪填充 Flood Fill：它是图遍历在二维网格上的直接应用，也是 GESP 七级考查的图论核心算法之一。

59.1 图的定义

在数学中，图通常表示为：

G=(V,E)G = (V, E)

其中：

  • VV（Vertex set）是顶点集，一个非空的有限集合，每个元素称为一个顶点（或节点）；
  • EE（Edge set）是边集，由顶点之间的连接关系构成，每条边表示两个顶点之间的关联。

例如，一个具有 5 个顶点、5 条边的无向图可表示为 V={0,1,2,3,4}V=\{0,1,2,3,4\}，E={(0,1),(0,2),(1,3),(1,4),(2,4)}E=\{(0,1),(0,2),(1,3),(1,4),(2,4)\}，其结构如下：

无向图示例 G=(V,E)

59.2 图的种类

59.2.1 无向图

无向图中，边是无方向的。连接顶点 uu 和 vv 的边写作 (u,v)(u, v)，且 (u,v)(u, v) 与 (v,u)(v, u) 代表同一条边。

示例：社交好友关系——若 A 是 B 的好友，则 B 也是 A 的好友，属于无向关联。

59.2.2 有向图

有向图的边带有方向。从 uu 指向 vv 的有向边记作 ⟨u,v⟩\langle u, v\rangle，其中 uu 为起点（尾），vv 为终点（头）。有向边 ⟨u,v⟩\langle u, v\rangle 与 ⟨v,u⟩\langle v, u\rangle 不是同一条边。

示例：网页超链接——A 链接到 B，并不代表 B 一定链接到 A。

59.2.3 加权图与无权图

  • 无权图：边只表示"是否相连"，没有额外数值。
  • 加权图：每条边带有一个权值（如距离、费用、时间），常用于最短路径等问题。权重通常用一个数值表示，例如 graph[u][v] = w 表示边 ⟨u,v⟩\langle u, v\rangle 的权值为 ww。

在 GESP 七级的图遍历与 Flood Fill 考查中，主要接触无权图和**网格（隐含边权为 1）**两种形态。

59.3 图节点的度的概念

"度"（Degree）刻画了一个顶点与其他顶点的连接紧密程度。

59.3.1 无向图的度

顶点 vv 的度 deg(v)deg(v)：与该顶点相连的边的总数。

握手定理（Handshaking Lemma）：无向图中，所有顶点度数之和等于边数的两倍，即：

∑v∈Vdeg(v)=2∣E∣\sum_{v \in V} deg(v) = 2|E|

推论：无向图所有顶点的度数之和必为偶数，因此"奇度顶点"的个数一定是偶数。

59.3.2 有向图的度

有向图把度拆分为"入度"和"出度"：

  • 入度 inDegree(v)inDegree(v)：以该顶点为终点的有向边数量；
  • 出度 outDegree(v)outDegree(v)：以该顶点为起点的有向边数量；
  • 总度：deg(v)=inDegree(v)+outDegree(v)deg(v) = inDegree(v) + outDegree(v)。

性质：所有顶点入度总和 = 所有顶点出度总和 = 图的总边数，即：

∑v∈VinDegree(v)=∑v∈VoutDegree(v)=∣E∣\sum_{v \in V} inDegree(v) = \sum_{v \in V} outDegree(v) = |E|

59.4 图的数据结构表示

在程序中表示图，常见两种存储方式：邻接矩阵和邻接表。

59.4.1 邻接矩阵

使用二维数组 graph[n][n] 存储图，nn 为顶点总数。

  • 无向图：graph[i][j] = graph[j][i]（对称）；
  • 有向图：仅当 ⟨i,j⟩\langle i, j\rangle 存在时 graph[i][j] 标记为 1（或权重），否则为 0（或无穷大）；
  • 优点：判断两点是否相连为 O(1)O(1)；
  • 缺点：空间复杂度 O(n2)O(n^2)，稀疏图浪费严重。
#include <cstdio>
#define MAX_VERTEX 5

// 初始化无向图邻接矩阵
void InitUndirectedGraph(int graph[MAX_VERTEX][MAX_VERTEX]) {
    for (int i = 0; i < MAX_VERTEX; i++) {
        for (int j = 0; j < MAX_VERTEX; j++) {
            graph[i][j] = 0;
        }
    }
    // 添加无向边（每条边存两次）
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;
    graph[2][4] = graph[4][2] = 1;
}

int main() {
    int graph[MAX_VERTEX][MAX_VERTEX];
    InitUndirectedGraph(graph);
    printf("无向图邻接矩阵:\n");
    for (int i = 0; i < MAX_VERTEX; i++) {
        for (int j = 0; j < MAX_VERTEX; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
    return 0;
}

59.4.2 邻接表

用"数组 + 链表"组合存储：数组下标代表顶点，每个顶点挂载一条链表，存储与它相邻的顶点。

  • 无向图：每条边存两次；有向图：仅起点的链表存储该边；
  • 优点：稀疏图节省空间，空间复杂度 O(n+e)O(n + e)；
  • 缺点：判断两点是否连边需要遍历链表，效率偏低（平均 O(deg(v))O(deg(v))）。
#include <cstdio>
#include <cstdlib>

// 邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 邻接表头结点
typedef struct AdjList {
    Node* head;
} AdjList;

// 图结构
typedef struct Graph {
    int numVertices;
    AdjList* adjLists;
} Graph;

// 创建链表节点
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建空图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = (AdjList*)malloc(vertices * sizeof(AdjList));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i].head = NULL;
    }
    return graph;
}

// 添加无向边
void addUndirectedEdge(Graph* graph, int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = graph->adjLists[u].head;
    graph->adjLists[u].head = newNode;

    newNode = createNode(u);
    newNode->next = graph->adjLists[v].head;
    graph->adjLists[v].head = newNode;
}

// 打印邻接表
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        printf("顶点%d的邻接表: ", v);
        Node* temp = graph->adjLists[v].head;
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Graph* graph = createGraph(5);
    addUndirectedEdge(graph, 0, 1);
    addUndirectedEdge(graph, 0, 2);
    addUndirectedEdge(graph, 1, 3);
    addUndirectedEdge(graph, 1, 4);
    addUndirectedEdge(graph, 2, 4);
    printGraph(graph);
    return 0;
}

59.4.3 两种表示方式的选择

表示方式空间复杂度查边效率遍历邻点适用场景
邻接矩阵O(n2)O(n^2)O(1)O(1)O(n)O(n)顶点少、边稠密
邻接表O(n+e)O(n + e)O(deg(v))O(deg(v))O(deg(v))O(deg(v))顶点多、边稀疏（更常用）

经验法则：当边数 ee 接近 n2n^2（稠密图）用邻接矩阵；当 ee 远小于 n2n^2（稀疏图）用邻接表。在 DFS/BFS/Flood Fill 中，邻接表或"网格的隐式邻居"是主流选择。

59.5 深度优先搜索 DFS

59.5.1 遍历逻辑

从起点出发，尽可能向深处走：访问一个顶点后，递归地去访问它未访问过的邻居；当当前顶点没有未访问的邻居（走到死胡同）时，回溯到上一个顶点继续探索。需要一个 visited 数组标记已访问顶点，防止在环上重复访问、陷入死循环。

59.5.2 递归实现

下面基于 59.4.2 的邻接表结构给出 DFS 递归遍历：

void DFSRecursive(int v, int visited[], Graph* graph) {
    visited[v] = 1;            // 标记已访问
    printf("%d ", v);
    Node* temp = graph->adjLists[v].head;
    while (temp) {
        int u = temp->vertex;
        if (!visited[u]) {     // 只递归未访问的邻居
            DFSRecursive(u, visited, graph);
        }
        temp = temp->next;
    }
}

59.5.3 非递归（栈）实现

当图很深时，递归可能栈溢出，可用显式栈模拟：

void DFSNonRecursive(int start, Graph* graph) {
    int numVertices = graph->numVertices;
    int visited[numVertices];
    for (int i = 0; i < numVertices; i++) visited[i] = 0;

    int stack[numVertices];
    int top = -1;
    visited[start] = 1;
    stack[++top] = start;
    printf("DFS非递归遍历顺序:");
    while (top != -1) {
        int v = stack[top--];
        printf("%d ", v);
        Node* temp = graph->adjLists[v].head;
        // 先把未访问邻居暂存，再逆序压栈，保证与递归顺序一致
        int tempStack[numVertices];
        int tempTop = -1;
        while (temp) {
            int u = temp->vertex;
            if (!visited[u]) {
                visited[u] = 1;
                tempStack[++tempTop] = u;
            }
            temp = temp->next;
        }
        while (tempTop != -1) stack[++top] = tempStack[tempTop--];
    }
    printf("\n");
}

59.5.4 适用场景

DFS 擅长"一条路走到底"，常用于：连通性/连通块判断、环检测、拓扑排序、迷宫一条路径查找。注意：DFS 不能保证求出无权图最短路径（它先深后广，路径长度无保证）。

59.6 广度优先搜索 BFS

59.6.1 遍历逻辑

从起点出发逐层扩散：使用队列存储"待访问顶点"，先访问起点，再把起点的所有未访问邻居入队；之后每次从队首取出一个顶点并访问它，同时把它未访问的邻居入队。如此保证"同一层全部访问完才进入下一层"，按"由近及远"的顺序遍历。

59.6.2 代码实现

void BFS(int start, Graph* graph) {
    int numVertices = graph->numVertices;
    int visited[numVertices];
    for (int i = 0; i < numVertices; i++) visited[i] = 0;

    int queue[numVertices];
    int front = 0, rear = 0;
    visited[start] = 1;
    queue[rear++] = start;
    printf("BFS遍历顺序:");
    while (front < rear) {
        int v = queue[front++];
        printf("%d ", v);
        Node* temp = graph->adjLists[v].head;
        while (temp) {
            int u = temp->vertex;
            if (!visited[u]) {
                visited[u] = 1;
                queue[rear++] = u;
            }
            temp = temp->next;
        }
    }
    printf("\n");
}

59.6.3 适用场景（无权图最短路径）

BFS 按层扩散的特性，使其天然适合求无权图（或边权均为 1 的图）的最短路径——第一次到达某个顶点时的步数即为最短距离。也常用于：连通区域统计、层级遍历、Flood Fill（见 59.7）。

59.7 泛洪填充 Flood Fill

59.7.1 什么是 Flood Fill（定义与本质）

Flood Fill（泛洪填充） 是图遍历在**二维网格（Grid）**上的应用。把网格看作一张图：

  • 每个单元格（格点）是一个顶点；
  • 两个单元格若上下左右相邻，则它们之间有一条边（即四邻域连接）；
  • 从一个"种子单元格"出发，沿着边访问所有连通且满足条件（如颜色相同）的单元格，并对它们执行某种操作（最常见的是"重新着色"）。

因此，Flood Fill 的本质就是：在网格图上求"与种子点连通的同色连通块"，并对该连通块统一处理。它是 BFS/DFS 的直接套用，区别只是"邻居"由"邻接表"变成了"上下左右四个方向"。

59.7.2 二维网格建模（单元格=顶点，四邻域=边）

网格中位置 (x,y)(x, y) 的合法邻居只有四个方向：上 (x−1,y)(x-1, y)、下 (x+1,y)(x+1, y)、左 (x,y−1)(x, y-1)、右 (x,y+1)(x, y+1)，统称四邻域（4-neighbor）。Flood Fill 每次只向这四个方向扩散，斜对角不算相邻。

Flood Fill 四邻域方向

59.7.3 DFS 实现（完整示例）

下面给出一个可独立运行的 Flood Fill 程序：从起点 (0,0)(0,0) 出发，把与起点连通、且颜色等于 oldColor 的所有单元格重新染成 newColor。为方便演示，用二维数组 int grid[ROW][COL] 表示网格，0 表示阻隔、1 表示待填充区域。

#include <cstdio>
#define ROW 4
#define COL 5

// 四邻域方向：上、下、左、右
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// DFS 版 Flood Fill：把从 (x,y) 出发、颜色为 oldColor 的连通块染成 newColor
void floodFillDFS(int grid[ROW][COL], int x, int y, int oldColor, int newColor) {
    // 1. 越界检查
    if (x < 0 || x >= ROW || y < 0 || y >= COL) return;
    // 2. 颜色不符（已不是目标连通块）则停止
    if (grid[x][y] != oldColor) return;
    // 3. 染色当前格
    grid[x][y] = newColor;
    // 4. 向四个方向递归扩散
    for (int i = 0; i < 4; i++) {
        floodFillDFS(grid, x + dirs[i][0], y + dirs[i][1], oldColor, newColor);
    }
}

void printGrid(int grid[ROW][COL]) {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            printf("%d ", grid[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int grid[ROW][COL] = {
        {1, 1, 0, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 0, 0, 1, 0},
        {0, 0, 0, 0, 0}
    };
    printf("填充前网格:\n");
    printGrid(grid);
    floodFillDFS(grid, 0, 0, 1, 2);   // 从(0,0)把连通的 1 染成 2
    printf("填充后网格:\n");
    printGrid(grid);
    return 0;
}

运行结果示意（左为填充前，右为填充后；注意右侧那些不连通的 1 没有被染色）：

Flood Fill 前后对比

59.7.4 BFS 实现（完整示例）

用队列代替递归，避免深层递归栈溢出，更适合大规模网格：

#include <cstdio>
#define ROW 4
#define COL 5

typedef struct Point { int x; int y; } Point;

int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// BFS 版 Flood Fill
void floodFillBFS(int grid[ROW][COL], int startX, int startY, int oldColor, int newColor) {
    if (startX < 0 || startX >= ROW || startY < 0 || startY >= COL) return;
    if (grid[startX][startY] != oldColor) return;

    Point queue[ROW * COL];
    int front = 0, rear = 0;
    queue[rear++] = {startX, startY};
    grid[startX][startY] = newColor;   // 入队即染色，防止重复入队

    while (front < rear) {
        Point cur = queue[front++];
        for (int i = 0; i < 4; i++) {
            int x = cur.x + dirs[i][0];
            int y = cur.y + dirs[i][1];
            if (x >= 0 && x < ROW && y >= 0 && y < COL && grid[x][y] == oldColor) {
                grid[x][y] = newColor;
                queue[rear++] = {x, y};
            }
        }
    }
}

59.7.5 DFS 与 BFS 对比（优缺点、如何选择）

对比项DFS（递归）BFS（队列）
代码复杂度简洁，几行递归较长，需维护队列与方向数组
空间占用递归深度 = 栈深度，深网格易栈溢出队列最大约 O(连通块面积)O(连通块面积)，更安全
访问顺序一条路走到底由近及远、按层扩散
适用规模小规模网格/连通块大规模网格、求最短路/最小步数
典型用途图像油漆桶、连通块标记迷宫最短路径、岛屿扩展

选择建议：网格不大、追求代码简短用 DFS；网格很大或需要"最短步数/最少操作"时用 BFS。注意 BFS 必须在入队时立即标记已访问（如本例染色），否则同一格可能被多次入队导致超时。

59.7.6 应用一：连通块 / 岛屿数量（经典真题风格示例）

问题描述（典型竞赛/考试题型）：给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿总是被水包围，且水平/竖直相邻的陆地连成同一个岛屿（斜对角不算）。

思路：每遇到一个 '1'，就说明发现了一个新岛屿；用一次 Flood Fill 把与它连通的所有 '1' 全部"沉掉"（改为 '0' 标记已访问），这样该岛屿就不会被重复计数。最终数出进行了几次 Flood Fill，即为岛屿数。

#include <vector>
using namespace std;

class Solution {
private:
    int rows, cols;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // Flood Fill：把与 (x,y) 连通的陆地整块沉掉
    void dfs(vector<vector<char>>& grid, int x, int y) {
        if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] != '1')
            return;
        grid[x][y] = '0';   // 标记已访问（沉岛）
        for (int i = 0; i < 4; i++) {
            dfs(grid, x + dirs[i][0], y + dirs[i][1]);
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        rows = grid.size();
        if (rows == 0) return 0;
        cols = grid[0].size();
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {   // 发现新岛屿
                    count++;
                    dfs(grid, i, j);        // 用 Flood Fill 沉掉整座岛
                }
            }
        }
        return count;
    }
};

小例子：对下方网格，左上两块 '1' 互不连通，因此岛屿数为 2：

1 1 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 1 1

59.7.7 应用二：图像填充、迷宫、地图连通区域

  • 画图软件"油漆桶"：点击某像素，把同色连通区域换成新颜色——正是 59.7.3 的 floodFillDFS 原型。
  • 迷宫连通性 / 最短路：把迷宫格点当网格，墙为阻隔、路为可走，用 Flood Fill 判断两格是否连通，用 BFS 求最少步数。
  • 地图连通区域统计：如统计一片海域中有多少个独立湖面、多少块大陆，本质都是"数连通块数量"，与 59.7.6 完全相同。

59.7.8 时间与空间复杂度分析

设网格大小为 R×CR \times C，每个单元格最多被访问一次：

  • 时间复杂度：O(R×C)O(R \times C)（最坏遍历整个网格一次）；
  • 空间复杂度：
    • DFS：递归调用栈深度最坏为 O(R×C)O(R \times C)（一条蛇形长连通块），易栈溢出；
    • BFS：队列最多同时存 O(R×C)O(R \times C) 个点。

若网格非常大（如 1000×10001000 \times 1000），优先用 BFS 或将 DFS 改为显式栈，避免递归爆栈。

59.8 选择题练习

参考答案与解析（点击展开）

  1. B —— 无向图中每条边贡献 2 个度，因此所有顶点度数之和 = 2∣E∣2|E|，是边数的两倍。

  2. B —— 邻接矩阵用 n×nn \times n 的二维数组，空间复杂度固定为 O(n2)O(n^2)，与边数无关。

  3. B —— Flood Fill 核心是在网格上找出"同色连通块"并统一处理，最典型的用途是图像/区域的连通填充与统计。

  4. A —— BFS 按层由近及远扩散，第一次到达某点时的步数即最短距离，因此能求无权图最短路径；拓扑排序、环检测更依赖 DFS。

  5. A —— 二维网格的 Flood Fill 只向**上下左右（四邻域）**扩散；八方向需额外加 4 个斜对角，不属于标准四邻域。

  6. B —— DFS 用递归/栈"一条路走到底"，代码短但递归深度过大时可能栈溢出；BFS 用队列更稳，适合大规模网格。

  1. 无向图中，所有顶点的度数之和等于（　　）。

    • A. 边数 ∣E∣|E|
    • B. 2∣E∣2|E|（边数的两倍）
    • C. 顶点数 ∣V∣|V|
    • D. 0

  2. 用邻接矩阵存储有 nn 个顶点的图，其空间复杂度为（　　）。

    • A. O(n)O(n)
    • B. O(n2)O(n^2)
    • C. O(n+e)O(n + e)
    • D. O(1)O(1)

  3. Flood Fill（泛洪填充）算法主要用于解决（　　）。

    • A. 单源最短路径
    • B. 二维网格的连通区域填充与统计
    • C. 数组排序
    • D. 二分查找

  4. 关于 BFS 与最短路径，下列说法正确的是（　　）。

    • A. BFS 可求无权图（边权均为 1）的最短路径
    • B. BFS 只能用于有向图
    • C. DFS 比 BFS 更适合求最短路
    • D. BFS 无法统计连通块

  5. 在二维网格上做标准 Flood Fill 时，一个单元格的"邻居"通常指（　　）。

    • A. 上下左右四个方向
    • B. 周围八个方向（含对角）
    • C. 仅右边一格
    • D. 仅对角线方向

  6. 下列关于 DFS 实现 Flood Fill 的说法，正确的是（　　）。

    • A. DFS 一定比 BFS 更快
    • B. 递归版在网格很大、连通块很深时可能栈溢出
    • C. DFS 不能用于连通块统计
    • D. DFS 不需要 visited 标记
SShowball OI知识手册