图详解：节点与边的连接艺术

图是描述"关系"的终极数据结构——社交网络、地图导航、依赖管理都离不开它

图在算法题中出现的频率很高，但很多人觉得它比树难理解。其实图可以看作是树的"升级版"——树是没有环的图，图则更加灵活，节点之间可以任意连接。

掌握图的关键是：理解存储方式 + 熟练运用 DFS/BFS。这两个遍历算法是解决几乎所有图问题的基础。

什么是图

图由节点（顶点）和边组成。

    0 ---- 1
    |      |
    |      |
    3 ---- 2

节点：0, 1, 2, 3
边：(0,1), (1,2), (2,3), (0,3)

图的分类

类型	特点	例子
无向图	边没有方向	社交网络的好友关系
有向图	边有方向	微博的关注关系
加权图	边有权重	地图上的距离
无环图(DAG)	有向图且没有环	课程依赖关系

graph LR
    subgraph 无向图
    A((0)) --- B((1))
    A --- C((2))
    B --- C
    end
    
    subgraph 有向图
    D((0)) --> E((1))
    E --> F((2))
    F --> D
    end
    
    style A fill:#FFE4B5
    style D fill:#87CEEB

图的存储方式

邻接矩阵

用二维数组表示，matrix[i][j] = 1 表示 i 和 j 之间有边。

// n个节点的图
vector<vector<int>> matrix(n, vector<int>(n, 0));

// 添加边 (无向图)
matrix[0][1] = 1;
matrix[1][0] = 1;

    0  1  2  3
0 [ 0  1  0  1 ]
1 [ 1  0  1  0 ]
2 [ 0  1  0  1 ]
3 [ 1  0  1  0 ]

优点：查询两点是否相连 O(1)
缺点：空间 O(n²)，稀疏图浪费空间

邻接表

每个节点存储它的邻居列表。

// n个节点的图
vector<vector<int>> adj(n);

// 添加边 (无向图)
adj[0].push_back(1);
adj[1].push_back(0);

0 -> [1, 3]
1 -> [0, 2]
2 -> [1, 3]
3 -> [0, 2]

优点：空间 O(V + E)，适合稀疏图
缺点：查询两点是否相连需要遍历

如何选择？

场景	推荐方式
稀疏图（边少）	邻接表
稠密图（边多）	邻接矩阵
需要快速判断连通	邻接矩阵
LeetCode 刷题	邻接表

图的遍历：DFS

深度优先搜索：一条路走到黑，走不通再回头。

基本模板

vector<bool> visited;

void dfs(vector<vector<int>>& adj, int node) {
    visited[node] = true;
    
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(adj, neighbor);
        }
    }
}

执行过程

图：
0 -- 1
|    |
3 -- 2

邻接表：
0 -> [1, 3]
1 -> [0, 2]
2 -> [1, 3]
3 -> [0, 2]

从节点0开始 DFS：

dfs(0)
├── visited[0] = true
├── 邻居1未访问 -> dfs(1)
│   ├── visited[1] = true
│   ├── 邻居0已访问，跳过
│   ├── 邻居2未访问 -> dfs(2)
│   │   ├── visited[2] = true
│   │   ├── 邻居1已访问，跳过
│   │   ├── 邻居3未访问 -> dfs(3)
│   │   │   ├── visited[3] = true
│   │   │   ├── 所有邻居已访问
│   │   │   └── 返回
│   │   └── 返回
│   └── 返回
├── 邻居3已访问，跳过
└── 返回

遍历顺序：0 -> 1 -> 2 -> 3

图的遍历：BFS

广度优先搜索：一层一层往外扩展，像水波一样。

基本模板

void bfs(vector<vector<int>>& adj, int start) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

执行过程

同样的图，从节点0开始 BFS：

初始：queue = [0], visited = {0}

Step 1: 取出0，加入邻居1, 3
        queue = [1, 3], visited = {0, 1, 3}

Step 2: 取出1，加入邻居2（0已访问）
        queue = [3, 2], visited = {0, 1, 3, 2}

Step 3: 取出3，邻居都已访问
        queue = [2]

Step 4: 取出2，邻居都已访问
        queue = []

遍历顺序：0 -> 1 -> 3 -> 2

DFS vs BFS

特点	DFS	BFS
数据结构	栈（递归/显式栈）	队列
空间复杂度	O(h) 递归深度	O(w) 最大宽度
适用场景	路径问题、连通性	最短路径、层级遍历
实现难度	递归简单	迭代简单

经典问题：岛屿数量

LeetCode 200: 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，请计算网格中岛屿的数量。

思路

遇到一个 ‘1’，就用 DFS/BFS 把整个岛屿标记掉，然后计数 +1。

DFS 解法

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    
    return count;
}

void dfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    
    // 边界检查 + 是否是陆地
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
        return;
    }
    
    grid[i][j] = '0';  // 标记为已访问
    
    // 四个方向
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

执行过程

grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

遍历过程：

(0,0)='1' -> DFS淹没整个岛屿 -> count=1
grid:
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 1

(2,2)='1' -> DFS淹没 -> count=2
grid:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1

(3,3)='1' -> DFS淹没整个岛屿 -> count=3
grid:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

答案：3

时间复杂度：O(m × n)
空间复杂度：O(m × n) 最坏情况递归深度

经典问题：课程表（拓扑排序）

LeetCode 207: 给定课程总数和先修关系，判断是否可能完成所有课程。

思路

这是一个检测有向图是否有环的问题。如果有环，说明存在循环依赖，无法完成。

可以用 DFS 检测环 或 BFS 拓扑排序（Kahn算法）。

BFS 拓扑排序

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> indegree(numCourses, 0);
    vector<vector<int>> adj(numCourses);
    
    // 建图 + 计算入度
    for (auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        indegree[p[0]]++;
    }
    
    // 入度为0的节点入队
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    
    int count = 0;
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        count++;
        
        // 删除这个节点的出边
        for (int next : adj[course]) {
            if (--indegree[next] == 0) {
                q.push(next);
            }
        }
    }
    
    return count == numCourses;
}

执行过程

numCourses = 4
prerequisites = [[1,0], [2,0], [3,1], [3,2]]

含义：
0 -> 1 -> 3
0 -> 2 -> 3

建图后：
adj[0] = [1, 2]
adj[1] = [3]
adj[2] = [3]
adj[3] = []

入度：[0, 1, 1, 2]

初始队列：[0]（入度为0）

Step 1: 取出0，count=1
        删除0的出边，更新入度
        入度变为 [0, 0, 0, 2]
        节点1, 2入队
        queue = [1, 2]

Step 2: 取出1，count=2
        入度变为 [0, 0, 0, 1]
        queue = [2]

Step 3: 取出2，count=3
        入度变为 [0, 0, 0, 0]
        节点3入队
        queue = [3]

Step 4: 取出3，count=4
        queue = []

count(4) == numCourses(4) -> true，可以完成！

经典问题：克隆图

LeetCode 133: 深拷贝一个无向图。

思路

用 HashMap 记录"旧节点 -> 新节点"的映射，DFS 遍历时创建新节点。

class Node {
public:
    int val;
    vector<Node*> neighbors;
};

unordered_map<Node*, Node*> visited;

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    
    // 如果已经克隆过，直接返回
    if (visited.count(node)) {
        return visited[node];
    }
    
    // 创建新节点
    Node* clone = new Node(node->val);
    visited[node] = clone;
    
    // 递归克隆邻居
    for (Node* neighbor : node->neighbors) {
        clone->neighbors.push_back(cloneGraph(neighbor));
    }
    
    return clone;
}

经典问题：最短路径

LeetCode 1091: 在 n×n 的网格中，找从左上角到右下角的最短路径（可以走8个方向）。

思路

BFS 天然适合求无权图的最短路径——第一次到达终点时的步数就是最短距离。

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
    
    vector<pair<int,int>> dirs = {
        {-1,-1}, {-1,0}, {-1,1},
        {0,-1},          {0,1},
        {1,-1},  {1,0},  {1,1}
    };
    
    queue<pair<int,int>> q;
    q.push({0, 0});
    grid[0][0] = 1;  // 标记距离（同时起到visited作用）
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        if (x == n-1 && y == n-1) {
            return grid[x][y];
        }
        
        for (auto [dx, dy] : dirs) {
            int nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                grid[nx][ny] = grid[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1;
}

常见技巧总结

1. 方向数组

// 四方向
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// 八方向
vector<pair<int,int>> dirs = {
    {-1,-1}, {-1,0}, {-1,1},
    {0,-1},          {0,1},
    {1,-1},  {1,0},  {1,1}
};

2. 建图技巧

// 边列表 -> 邻接表
vector<vector<int>> adj(n);
for (auto& edge : edges) {
    adj[edge[0]].push_back(edge[1]);
    adj[edge[1]].push_back(edge[0]);  // 无向图
}

3. 避免重复访问

// 方法1：visited 数组
vector<bool> visited(n, false);

// 方法2：直接修改原数组（适用于网格）
grid[i][j] = '#';  // 标记为已访问

思维导图

graph TD
    A[图] --> B[存储方式]
    A --> C[遍历算法]
    A --> D[经典问题]
    
    B --> B1[邻接矩阵]
    B --> B2[邻接表]
    
    C --> C1[DFS 深度优先]
    C --> C2[BFS 广度优先]
    
    D --> D1[岛屿问题]
    D --> D2[拓扑排序]
    D --> D3[最短路径]
    D --> D4[连通分量]
    
    style A fill:#FFE4B5
    style C fill:#90EE90
    style D fill:#87CEEB

总结

核心要点

邻接表是刷题首选：空间效率高，适合大多数场景
DFS 用于路径/连通性问题：递归实现简洁
BFS 用于最短路径问题：层序遍历的天然优势
拓扑排序检测环：入度为 0 的节点逐个删除

LeetCode 推荐题单

入门：

200 岛屿数量
733 图像渲染
547 省份数量

进阶：

207 / 210 课程表
133 克隆图
1091 二进制矩阵最短路径

挑战：

743 网络延迟时间（Dijkstra）
787 K站中转最便宜航班
127 单词接龙

推荐阅读：

常见数据结构-二叉树 - 树是无环连通图的特例
LeetCode 图专题