Module: Cerca in profondità. DFS


Problem

2/12

DFS: Avvia (Python)

Theory Click to read/hide

DFS DFS
La prima ricerca in profondità (DFS) è uno dei principali algoritmi sui grafici. L'algoritmo viene eseguito in O(N + M).
 
Algoritmo
Per cominciare, partiamo dall'alto, consideriamo i figli di questo top, e se non li abbiamo mai inseriti, allora iniziamo DFS da loro.


Problem

Scrivi una procedura def dfs(v) che attraversi la profondità di un grafo non orientato dal vertice iniziale S e generi tutti i vertici in ordine di attraversamento, a partire dal vertice < code>S separati da uno spazio su una riga.

La prima riga contiene tre numeri N  - il numero di vertici nel grafico, M - il numero di spigoli, S - il punto iniziale vertice. Nelle seguenti righe M, 2 variabili Ui e Vi sono forniti , descrizione degli spigoli del grafo. Tutti i numeri inseriti non superano 1000.

Visualizza tutti i vertici in ordine di attraversamento tramite DFS.

Nel programma precedente, V[i][j] significa che c'è un bordo tra i vertici i e j, e in l'array Visited contrassegniamo se abbiamo visitato questo picco. 
 
Usa 4 spazi per indicare il rientro.

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!