企业官网建设流程全解析

图论总结篇｜Graph Algorithms

一、图的基本概念与存储

图（Graph）由节点（Vertex）和边（Edge）组成。

根据题目可以分为：

• Directed Graph（有向图）：边有方向。
• Undirected Graph（无向图）：边没有方向。
• Weighted Graph（带权图）：每条边有权重。
• Unweighted Graph（无权图）：边不带权重，或者每条边权重相同。

1. 邻接矩阵（Adjacency Matrix）

使用二维数组graph[i][j]表示节点 i 和 j 之间是否存在边，或者记录边的权重。

• 空间复杂度：O(V²)
• 查询一条边是否存在：O(1)
• 遍历某个节点的邻居：O(V)
• 适合稠密图（Dense Graph）。

2. 邻接表（Adjacency List）

使用vector<vector<int>>等结构存储每个节点的邻居。

• 空间复杂度：O(V + E)
• 遍历某个节点的邻居：O(degree)
• 适合稀疏图（Sparse Graph）。

面试建议：优先熟练掌握邻接表，同时会写邻接矩阵。

二、DFS 与 BFS（最高优先级）

DFS 和 BFS 是图论最基础、最常考的两种搜索算法。

1. DFS（Depth-First Search）

深度优先搜索沿着一条路径不断深入，直到无法继续，再返回之前的节点探索其他路径。

常见应用：

• 判断连通性（Connectivity）
• 岛屿问题（Number of Islands）
• 寻找所有路径（All Paths）
• 检测环（Cycle Detection）
• 图遍历（Graph Traversal）

DFS 与 Backtracking 的关系：

• 如果只是判断节点是否访问过，通常不需要手动恢复visited。
• 如果要枚举所有路径，通常需要维护当前路径，并在递归返回时撤销本次选择。

例如：

void dfs(int u) { visited[u] = true; for (int v : graph[u]) { if (!visited[v]) { dfs(v); } } }

时间复杂度：O(V + E)（使用邻接表）。

2. BFS（Breadth-First Search）

广度优先搜索使用队列（Queue），从起点开始逐层访问节点。

常见应用：

• 无权图最短路径
• 最少操作次数
• 岛屿问题
• 多源 BFS（Multi-source BFS）
• 层序遍历

queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } }

重要易错点：BFS 应该在入队时标记 visited，而不是出队时。

否则同一个节点可能被重复加入队列，造成大量无效操作。

DFS vs BFS

经典题目：

• LeetCode 200 — Number of Islands
• LeetCode 695 — Max Area of Island
• LeetCode 797 — All Paths From Source to Target
• LeetCode 994 — Rotting Oranges
• LeetCode 127 — Word Ladder

三、并查集（Union Find / DSU）

并查集主要用于解决**动态连通性（Dynamic Connectivity）**问题。

例如：

• 两个节点是否属于同一个连通分量？
• 添加一条边是否会形成环？
• 一个图有几个连通分量？

核心操作

1. find(x)：查找节点所属集合的根节点。
2. unite(x, y)：合并两个集合。
3. connected(x, y)：判断两个节点是否属于同一个集合。

核心优化

Path Compression（路径压缩）

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }

还可以使用 Union by Rank / Size（按秩或按大小合并）。

两者结合后，单次操作的均摊复杂度接近 O(1)，严格来说为 O(α(V))。

什么时候使用并查集？

看到下面的关键词，可以考虑 DSU：

• Connected Components
• Redundant Connection
• Undirected Cycle Detection
• Merge Groups
• Minimum Spanning Tree

注意：普通并查集主要适用于无向图连通性，不能直接解决所有有向图环检测问题。

经典题目：

• LeetCode 547 — Number of Provinces
• LeetCode 684 — Redundant Connection
• LeetCode 1319 — Number of Operations to Make Network Connected

四、最小生成树（Minimum Spanning Tree）

MST 用于在连通、无向、带权图中，使用最小总边权连接所有节点，并且不形成环。

主要有两种算法。

1. Prim Algorithm

Prim 从一个节点开始，不断选择连接当前生成树与未访问节点的最小权重边。

核心思路：

1. 选择距离当前生成树最近的节点。
2. 将节点加入生成树。
3. 更新其他节点到生成树的最小距离。

核心数组：

minDist[v]：节点 v 到当前生成树的最小连接边权重。

使用邻接矩阵的朴素版本：

时间复杂度：O(V²)。

2. Kruskal Algorithm

Kruskal 从边出发，按照边的权重从小到大选择。

步骤：

1. 对全部边按权重排序。
2. 使用 Union Find 判断两个端点是否已经连通。
3. 如果不连通，则选择这条边并合并集合。
4. 直到选择 V−1 条边。

复杂度：O(E log E)，其中 E 是边的数量。

Prim vs Kruskal

面试建议：Kruskal 要会写，Prim 理解核心思路。

经典题目：

• LeetCode 1584 — Min Cost to Connect All Points

五、拓扑排序（Topological Sort）

拓扑排序用于DAG（Directed Acyclic Graph，有向无环图）。

它的目标是找到一个节点排列，使得每条有向边u → v中，u 都出现在 v 之前。

常见应用：

• 课程先修关系
• 任务依赖
• 软件构建顺序
• 工作流调度

Kahn’s Algorithm（BFS）

核心思想：

1. 计算每个节点的入度（In-degree）。
2. 将入度为 0 的节点加入队列。
3. 取出节点，将其加入结果。
4. 将它指向的节点入度减 1。
5. 如果某个节点入度变成 0，则入队。

如果最终处理的节点数量小于总节点数量，说明图中存在环。

时间复杂度：O(V + E)。

经典题目：

• LeetCode 207 — Course Schedule
• LeetCode 210 — Course Schedule II

这两道题很值得反复练习。

六、最短路径算法（Shortest Path）

最短路径算法需要根据边权和题目限制来选择。

1. BFS

适用场景：无权图，或者所有边的权重相等且为正数。

时间复杂度：O(V + E)。

2. Dijkstra

适用场景：带权图，且边权非负。

核心思想：

不断确定当前距离起点最近的未处理节点，再更新其相邻节点的距离。

使用 Min Heap / Priority Queue：

时间复杂度：O((V + E) log V)（常见二叉堆邻接表实现的上界）。

面试建议：理解松弛操作（Relaxation），并掌握优先队列版本。

3. Bellman-Ford

适用场景：

• 允许负权边。
• 可以检测从起点可达的负权环。
• 限制最多经过多少条边的问题。

核心思想：

重复对所有边进行松弛（Relaxation），最多执行 V−1 轮。

时间复杂度：O(VE)。

4. Floyd-Warshall

适用场景：求所有节点对之间的最短距离（All-Pairs Shortest Paths）。

核心公式：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

使用三重循环，最外层必须是中间节点 k。

时间复杂度：O(V³)。

可以处理负权边，但如果存在相关负权环，最短路径可能没有有限解。

5. A* Search

A* 使用启发式函数来引导路径搜索。

f(n) = g(n) + h(n)

• g(n)：从起点到当前节点的实际代价。
• h(n)：从当前节点到目标的估计代价。
• f(n)：估计经过当前节点到目标的总代价。

适合路径规划、游戏 AI、机器人导航等问题。

普通 SDE Intern 面试优先级较低，理解原理即可。

最短路径算法速查表

七、图论面试的算法选择

遇到图论题，先问自己：

1. 题目是不是在找连通性或遍历？

• 连通区域 / 岛屿 → DFS / BFS
• 动态合并集合 → Union Find

2. 题目是不是在找路径？

• 所有路径 → DFS + Backtracking
• 无权最短路径 → BFS
• 非负权最短路径 → Dijkstra

3. 题目是不是在处理依赖？

• 课程安排 / 任务顺序 → Topological Sort

4. 题目是不是在寻找最低连接成本？

• 连接所有节点且总代价最小 → MST / Kruskal / Prim

注意区分 Minimum Spanning Tree 和 Shortest Path：最小生成树最小化连接所有节点的总成本，最短路径最小化两个节点之间的路径成本。

八、我的 SDE Internship 图论复习优先级

第一梯队：必须熟练手写

• DFS
• BFS
• Grid Traversal
• Backtracking
• Topological Sort

要求：能够在 20–30 分钟内独立完成典型 LeetCode Medium。

第二梯队：建议熟练掌握

• Union Find
• Dijkstra
• Kruskal
• Heap / Priority Queue

要求：能理解原理，自己写出模板，并解决经典题目。

第三梯队：理解即可

• Prim
• Bellman-Ford
• Floyd-Warshall
• A*

要求：知道何时使用、主要思路和时间复杂度。

对于普通 Backend / General SDE Internship，不需要一开始就在第三梯队投入大量时间。

九、最终复习 Checklist

• 能够使用邻接表和邻接矩阵表示图
• 能够独立实现 DFS 和 BFS
• 理解 DFS 中什么时候需要回溯
• 知道 BFS 为什么需要入队时标记 visited
• 能够用 BFS 求无权图最短路径
• 能够实现 Union Find + Path Compression
• 能够使用 Kahn 算法进行拓扑排序并检测环
• 能够实现 Dijkstra + Priority Queue
• 理解 Kruskal 如何结合 Union Find
• 能够根据边权条件选择最短路径算法
• 理解 Prim、Bellman-Ford、Floyd-Warshall 和 A* 的基本思路