如下简单介绍了基础图论算法，包含DFS、BFS、拓扑排序的知识点以及模板，不含图论的中、高级算法，内容仅供参考，如有错误，欢迎私信或评论区指正：
一、建图
默认优先使用邻接表 vector<vector<int>>
对于带权图，使用 vector<vector<pair<int, int>>>
仅在稠密图、全对全连边图、或需要快速边存在判断的情况下考虑邻接矩阵或哈希表等
二、DFS
（一）基础图遍历 / 连通性 DFS
一个节点只访问一次，不回溯，不构造、保存路径，只关心到达
适用场景：连通块、染色、Tarjan、拓扑
void dfs(int u) {
vis[u] = true;
for (int v : G[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
（二）路径枚举型 DFS + 回溯
在图中枚举所有从起点到终点的合法路径，保存所有路径 path
在一个图 graph[u] 中，从节点 u 出发，寻找所有到 target 的简单路径。适用于路径的构造或搜索
vector<vector<int>> ans;
vector<int> path;
vector<bool> visited(N, false);
void dfs(int u, int target) {
path.push_back(u);
if (u == target) {
ans.push_back(path); // 找到一条合法路径
} else {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v, target);
}
}
visited[u] = false;
}
path.pop_back(); // 回溯
}
问：为什么要回溯?
路径枚举DFS中的vis标记回溯是为了允许不同路径重复使用同一节点，path路径回溯是为了保存不同的路径
（三）组合型 DFS + 回溯
适用场景：从1~n中选出k个数，无重复，顺序不敏感（典型的组合问题）。不需要visited数组，因为通过start限制避免重复。适用组合树、搜索树、子集问题。
void dfs(int u, int start, int n, int k) {
if (u == k) {
ans.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
dfs(u + 1, i + 1, n, k);
path.pop_back();
}
}
（四）排列型 DFS + 回溯
适用场景：从n个元素中排列出所有可能，顺序敏感。适用全排列、八皇后、路径构造等问题。
使用场景：
1.图中路径枚举
2.需要保存输出所有可能解（不是只找一个解）
3.图是有向无环图（DAG）
vector<int> path;
vector<vector<int>> ans;
vector<int> vis(25, 0);
void dfs(int u, int n) {
if (u == n) {
ans.push_back(path);
return;
}
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
path.push_back(i);
vis[i] = true;
dfs(u + 1, n);
vis[i] = false;
path.pop_back();
}
}
对于初学者而言，理解DFS到底是如何进行图遍历的，尤为重要。可以通过如下的DFS+回溯图遍历路径解空间树辅助理解： 邻接表：graph = [[1, 2, 3, 5], [3, 4, 5], [4, 6], [4, 5, 6], [5, 6], [6], []]
0
├── 1
│ ├── 3
│ │ ├── 4
│ │ │ ├── 5
│ │ │ │ └── 6 -> [0,1,3,4,5,6]
│ │ │ └── 6 -> [0,1,3,4,6]
│ │ ├── 5
│ │ │ └── 6 -> [0,1,3,5,6]
│ │ └── 6 -> [0,1,3,6]
│ ├── 4
│ │ ├── 5
│ │ │ └── 6 -> [0,1,4,5,6]
│ │ └── 6 -> [0,1,4,6]
│ └── 5
│ └── 6 -> [0,1,5,6]
├── 2
│ ├── 4
│ │ ├── 5
│ │ │ └── 6 -> [0,2,4,5,6]
│ │ └── 6 -> [0,2,4,6]
│ └── 6 -> [0,2,6]
├── 3
│ ├── 4
│ │ ├── 5
│ │ │ └── 6 -> [0,3,4,5,6]
│ │ └── 6 -> [0,3,4,6]
│ ├── 5
│ │ └── 6 -> [0,3,5,6]
│ └── 6 -> [0,3,6]
└── 5
└── 6 -> [0,5,6]
三、BFS
（一）BFS层次遍历
需要外层for循环模拟层次，需要visited数组，适用于层数分析，如求最短路、最少天数
while (!q.empty()) {
int sz = q.size(); // 当前层节点数
for (int i = 0; i < sz; ++i) {
int u = q.front(); q.pop();
if (u == target) return step;
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
++step;
}
return -1; // target 不可达
（二）BFS非层次遍历
不需外层for循环，适用于可达性传播：染色问题 / 感染传播 / 遍历所有能到的点等
queue<int> q;
for (int src : sources) {
q.push(src);
visited[src] = true;
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
三、拓扑排序：
拓扑排序核心：入度（indegree）计数
初始时0入度的节点入队，过程中入度减到0则入队，也是因此不需要visited数组
（一）普通拓扑排序模板（Kahn）
非层次遍历，不需要外层for循环和visited数组，只用于DAG，可与状态合并传递算法结合用于DAG状态合并向后传播类问题
vector<vector<int>> graph(n);
vector<int> indeg(n, 0);
// 构建图与入度数组
for (auto& e : edges) {
graph[e[0]].push_back(e[1]);
indeg[e[1]]++;
}
// 入度为 0 的节点入队
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) q.push(i);
}
// 拓扑排序过程
while (!q.empty()) {
int cur = q.front(); q.pop();
for (int& next : graph[cur]) {
if (--indeg[next] == 0) q.push(next);
}
}
这是对于有向图而言的，那么对于无向图而言该怎么做呢？
无向图本身不适用拓扑排序，无向图通常通过把所有起点或邻居数为1的边际节点入队，开始层次BFS
（二）基于拓扑排序的状态传递（传递闭包）
利用拓扑序保证依赖关系，在遍历过程中进行状态的传递、合并或传播，"求所有关系"。
适用场景
- 求图中所有点对的可达性关系
- 预处理后快速查询祖先/后代关系
- 构建DAG的传递闭包矩阵
vector<int> indeg(n, 0);
for (int u = 0; u < n; ++u) {
for (int v : graph[u]) {
indeg[v]++;
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) q.push(i);
}
while (!q.empty()) {
int cur = q.front(); q.pop();
for(int& next : graph[cur]) { // 状态合并
pre[next].insert(cur); // 1.直接依赖：添加直接前驱
for(const int& p : pre[cur]) {
pre[next].insert(p); // 2.间接依赖（传递闭包）：合并所有间接前驱，使状态向后传播
}
if (--indeg[next] == 0) q.push(next); // 拓扑推进，入度为零可以入队
}
}
传递闭包的构造方法有两种
全源：Floyd-Warshall，复杂度 O(n^3)，适合稀疏图 DAG：拓扑排序 + 状态传递
（三）基于拓扑排序的的状态传递（动态规划）
DAG上DP = 拓扑排序的BFS + 状态转移
与普通BFS相比，适用于有权图的处理，用于寻找有依赖条件的最优解
用于某独立值在图中的扩散，本质是对节点状态进行拓扑序依赖下的最值更新传递，状态不是传统的数值型路径权重，而是 引用另一个节点的索引作为状态。
例题：LC851 （拓扑 + 状态传递 + DP） claude可视化演示
while(!q.empty()){
int c = q.front();
q.pop();
for(int i=0; i<person[c].size(); i++){
if(quiet[answer[c]] < quiet[answer[person[c][i]]]){
answer[person[c][i]] = answer[c]; // 有条件地更新
}
if(--indeg[person[c][i]] == 0){
q.push(person[c][i]);
}
}
}
四、总结
算法题目中，如何判断用哪个模型？
如果题目明确有层级关系，如最短路径、层数、天数 —— 用 BFS 层次模型
如果题目要求是否能到达、是否能遍历 —— BFS 非层次 结构足够
如果题目涉及前后依赖关系（如课程、构建），且图是DAG，每个节点状态可传递 —— 使用 拓扑排序 + 状态合并
关于visited[]数组的使用
几乎所有的图遍历算法都需要visited数组来防止重复访问，这是图遍历的基本要求，无论是DFS还是BFS，无论是有向图还是无向图。
拓扑排序（Kahn）是例外，它使用入度计数来控制访问顺序，天然避免了重复访问，因此不需要额外的visited数组。
在BFS的最短路径问题中，visited数组确保了每个节点第一次被访问时就锁定了它的最短距离，后续不再更新，这是BFS正确求解最短路径的关键。防止重复入队，确保最短路径等于层数。
如何区分BFS层次和非层次遍历
BFS根据是否需要距离信息分为两类：不需要距离时用非层次BFS，需要距离时用层次BFS（带外层for循环）。单、多源BFS，既可以是层次BFS（最短路），也可以是非层次的（腐烂橘子）， 其中，多源BFS将所有源点同时加入队列，利用队列的FIFO特性实现同步扩展，仍可以找到最短路
BFS
/ \
单源 BFS 多源 BFS
/ \ / \
非层次型 层次型 非层次型 层次型
如何判断有环
在拓扑排序中，可以统计处理的节点数量，如果少于总节点数则说明图中有环，在过程中用一个visitedCount变量累加，搜索结束以后再根据该变量是否等于结点数判断是否有环
更多中、高级图论算法知识将在后续文章展开，欢迎关注订阅！
京公网安备 11010502036488号