Module: 深入搜索。数字文件系统

Problem

2/12

深度优先搜索 (DFS) 是图上的主要算法之一。该算法在 O(N + M) 中运行。

首先，我们从顶部开始，考虑这个顶部的子项，如果我们从未输入过它们，那么我们从它们开始DFS。

编写一个程序def dfs(v)，从起始顶点S开始遍历无向图的深度，并按遍历顺序输出所有顶点，从顶点<开始code>S 在一行中以空格分隔。

第一行包含三个数字 N - 图中的顶点数，M - 边数，S - 起点顶点。在接下来的 M 行中，2 个变量 U_i 和 V_i 提供了 ，图边的描述。输入的所有数字不超过 1000。

通过 DFS遍历的顺序输出所有顶点。

上述程序中， V[i][j]表示顶点i和j之间有一条边，在数组 Visited 我们标记我们是否访问了这个峰。

使用 4 个空格表示缩进。

Python

Write the program below
def dfs(start):

n, m, s = map(int, input().split()) Visited = [False]*(n+1) V = [set() for i in range(n+1)] for i in range(m): u, v = map(int, input().split()) V[u].add(v) V[v].add(u) dfs(s)