2026 华为OD机试真题9月9日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

给定一个无向图，顶点编号从 1 到 n；从顶点 1 出发，进行深度优先搜索(DFS)，当某个顶点有多个邻接点时，按照编号从小到大的顺序依次访问，输出遍历过程中访问顶点的顺序。

1≤n≤100，0≤m≤100。若不连通，DFS 从顶点 1 出发无法遍历所有顶点，输出只包含可达顶点。输入保证没有自环如 (i,i)，即顶点到自身的边；同时输入保证不会有多条相同的边，如 (1,2) 出现两次。

2026 华为OD机试真题9月9日华为OD上机新系统考试真题 100 分题型

输入描述

• 整数 n, m：表示顶点数和边数；
• 二维数组 graph：每个元素有两个整数 u, v，表示 u 和 v 之间有一条无向边；

输出描述

• 数组：数组元素表示深度优先搜索访问顶点的顺序（从 1 开始）；

示例1

输入

6
5
[[1,2],[1,3],[2,4],[3,5],[3,6]]

输出

[1,2,4,3,5,6]

说明

• 从 1 出发，邻接点有 {2,3}，选小的 2
• 从 2 出发，邻接点有 {1,4}，1 已访问，选 4
• 4 没有未访问邻接点，回溯到 2，回溯到 1，下一个未访问的是 3
• 从 3 出发，邻接点有 {1,5,6}，1 已访问，选小的 5
• 5 没有未访问邻接点，回溯到 3，下一个未访问的是 6；6 结束，遍历完成。最终访问顺序为 [1,2,4,3,5,6]。

示例2

输入

5
2
[[1,2],[3,4]]

输出

[1,2]

说明

• 从 1 出发，邻接点有 {2}，选 2
• 从 2 出发，邻接点有 {1}，1 已访问，没有未访问邻接点，回溯到 1
• 1 没有其他未访问邻接点，遍历结束。顶点 3、4、5 与 1 不连通，无法到达，因此不输出。最终访问顺序为 [1,2]。

解题思路

核心思想

题目要求从顶点 1 开始做 DFS，并且每次优先访问编号更小的邻接点。可以先根据边列表建立无向图的邻接表，再把每个顶点的邻接表升序排序，最后从 1 开始递归 DFS。

相比邻接矩阵，邻接表更适合本题的 m <= 100 稀疏图场景，遍历时只需要查看真实存在的边。

算法步骤

1. 建立 n + 1 个邻接表，顶点编号从 1 到 n。
2. 对每条无向边 [u,v]，分别加入 u -> v 和 v -> u。
3. 将每个顶点的邻接表按编号升序排序。
4. 从顶点 1 开始 DFS：
   • 访问当前顶点并加入答案；
   • 按升序枚举邻接点；
   • 未访问过的邻接点继续递归。
5. 输出 DFS 访问顺序。

复杂度分析

设顶点数为 n，边数为 m。

• 时间复杂度：O(n + m log m)，主要来自邻接表排序和 DFS。
• 空间复杂度：`O(n +