先把每个点的邻接表按升序排序，再用逆序压栈实现非递归 DFS，用队列实现 BFS。
OJ: luogu
题目 ID: P5318
难度:入门
标签:图论DFSBFS排序python
日期: 2026-06-19 19:24
题意
给出一个有向图，从 1 号点出发，分别输出：
- 按题目要求进行的 DFS 遍历顺序
- 按题目要求进行的 BFS 遍历顺序
如果某一步有多个可选点，必须先访问编号较小的那个。
思路
最直接的做法就是照定义写 DFS 和 BFS。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
static vector<vector<int>> g;
static vector<int> vis;
static vector<int> dfs_order;
static vector<int> bfs_order;
void dfs(int u) {
vis[u] = 1;
dfs_order.push_back(u);
for (int v : g[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
g.assign(n + 1, {});
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
sort(g[i].begin(), g[i].end());
}
vis.assign(n + 1, 0);
dfs(1);
for (int x : dfs_order) {
cout << x << ' ';
}
cout << '\n';
fill(vis.begin(), vis.end(), 0);
queue<int> q;
q.push(1);
vis[1] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
bfs_order.push_back(u);
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
for (int x : bfs_order) {
cout << x << ' ';
}
cout << '\n';
return 0;
}brute.cpp 用递归 DFS 和普通队列 BFS 实现了最直观的版本，适合小图对拍。
真正需要注意的是访问顺序和栈深：
- 邻接表必须先按升序排序
- BFS 直接按升序扩展邻居即可
- 正式解里的 DFS 不建议用递归，因为
n可达1e5
这张图展示样例结构：
digraph G {
1 -> 2;
1 -> 3;
1 -> 4;
2 -> 5;
2 -> 6;
3 -> 7;
4 -> 7;
4 -> 8;
7 -> 8;
}
从图里可以看出，BFS 很自然是一层一层访问；而 DFS 则需要优先深入编号更小的后继。所以正式解采用“邻接表升序 + 逆序压栈”的方式，用显式栈模拟递归 DFS 的顺序。
Python 知识
deque的popleft()是，适合作为 BFS 队列。 - 非递归 DFS 用列表作栈；邻接表升序后以
reversed(graph[node])逆序压栈，弹出时才会优先访问小编号。 bytearray(n+1)比 Python 布尔列表更紧凑，适合十万点访问标记。- 逐行读入百万条边，避免
read().split()同时保留两百万个临时 token。 /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：deque队列和容器选择。/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：递归深度与输入内存。
代码
python
import sys
from collections import deque
def main():
read = sys.stdin.buffer.readline
n, m = map(int, read().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, read().split())
graph[u].append(v)
for neighbors in graph:
neighbors.sort()
visited = bytearray(n + 1)
dfs_order = []
stack = [1]
while stack:
node = stack.pop()
if visited[node]:
continue
visited[node] = 1
dfs_order.append(node)
stack.extend(reversed(graph[node]))
visited = bytearray(n + 1)
visited[1] = 1
bfs_order = []
queue = deque([1])
while queue:
node = queue.popleft()
bfs_order.append(node)
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = 1
queue.append(neighbor)
print(*dfs_order)
print(*bfs_order)
if __name__ == "__main__":
main()复杂度
建图后需要对各邻接表排序，然后各做一次 DFS 和 BFS。时间复杂度上界为
总结
这题本身不难，关键在两个实现细节：邻接表要排序，非递归 DFS 要逆序压栈。把这两个点处理好，答案就稳定了。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
