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


Problem

2/12

DFS：开始（Python）

Theory Click to read/hide

DFS DFS
深度优先搜索 (DFS) 是图上的主要算法之一。该算法在 O(N + M) 中运行。
 
算法
首先，我们从顶部开始，考虑这个顶部的子项，如果我们从未输入过它们，那么我们从它们开始DFS。


Problem

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

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

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

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

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
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)

     

Program check result

To check the solution of the problem, you need to register or log in!