Implementare la DFS per i grafi
In questo esercizio implementerai un algoritmo di depth first search per attraversare un grafo.
Ricorda i passaggi:
- Parti da un vertice qualsiasi
- Aggiungi il vertice all’elenco dei vertici visitati
- Per ogni vertice adiacente del nodo corrente
- Se è già stato visitato -> ignoralo
- Se non è stato visitato -> esegui ricorsivamente la DFS
Per aiutarti a testare il tuo codice, il seguente grafo è stato caricato usando un dizionario.
graph = {
'0' : ['1','2'],
'1' : ['0', '2', '3'],
'2' : ['0', '1', '4'],
'3' : ['1', '4'],
'4' : ['2', '3']
}
Questo esercizio fa parte del corso
Strutture dati e algoritmi in Python
Istruzioni dell'esercizio
- Verifica che
current_vertexnon sia ancora stato visitato. - Aggiungi
current_vertexavisited_vertices. - Chiama
dfs()in modo ricorsivo passandole i valori appropriati.
Esercizio pratico interattivo
Prova a risolvere questo esercizio completando il codice di esempio.
def dfs(visited_vertices, graph, current_vertex):
# Check if current_vertex hasn't been visited yet
if current_vertex not in ____:
print(current_vertex)
# Add current_vertex to visited_vertices
____.add(____)
for adjacent_vertex in graph[current_vertex]:
# Call recursively with the appropriate values
____(____, ____, ____)
dfs(set(), graph, '0')