Module: Recherche en profondeur. DFS


Problem

2/12

DFS : Démarrer (Python)

Theory Click to read/hide

DFS DFS
La recherche en profondeur d'abord (DFS) est l'un des principaux algorithmes sur les graphes. L'algorithme s'exécute en O(N + M).
 
Algorithme
Pour commencer, nous partons du sommet, considérons les enfants de ce sommet, et si nous ne les avons jamais saisis, nous démarrons DFS à partir d'eux.


Problem

Écrivez une procédure def dfs(v) qui traverse la profondeur d'un graphe non orienté à partir du sommet de départ S et affiche tous les sommets dans l'ordre de parcours, en commençant au sommet < code>S séparés par un espace sur une ligne.

La première ligne contient trois nombres N  - le nombre de sommets dans le graphe, M - le nombre d'arêtes, S - le début sommet. Dans les lignes M suivantes, 2 variables Ui et Vi sont fournis , description des arêtes du graphe. Tous les nombres dans l'entrée ne dépassent pas 1000.

Afficher tous les sommets dans l'ordre de traversée par DFS.

Dans le programme ci-dessus, V[i][j] signifie qu'il y a une arête entre les sommets i et j, et dans le tableau Visited nous marquons si nous avons visité ce pic. 
 
Utilisez 4 espaces pour indiquer l'indentation.

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!