20260906-图的遍历（N0073）- 算法机考高频题型 · 华为OD / dfs题解 | AlgoMooc

N0073. 20260906-图的遍历

中等

通过率 83% · 提交 6 · 通过 5

100分华为ODdfs

本题改编自算法机考高频题型 · 考点：100分 / 华为OD · 难度：中等

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

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

这类题属于算法机考高频题型中「100分 / 华为OD」方向的高频题型，通常考察对「100分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

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

输出描述

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

示例

示例 1

输入示例

输出示例

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]。

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

未登录也能直接「运行」调试;「提交」判题需微信登录,你写的代码会自动保留、登录后回到本题继续。

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List

class Solution:
    def dfsTraversal(self, n: int, m: int, graph: List[List[int]]) -> List[int]:
        return []

if __name__ == "__main__":
    import sys
    input = sys.stdin.readline
    
    line = input().strip()
    while line == '':
        line = input().strip()
    n, m = map(int, line.split())
    
    graph = []
    for _ in range(m):
        line = input().strip()
        while line == '':
            line = input().strip()
        u, v = map(int, line.split())
        graph.append([u, v])
    
    sol = Solution()
    result = sol.dfsTraversal(n, m, graph)
    
    print(','.join(map(str, result)))

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交