Ricerca in profondità DFS in Python
DFS usa ricorsione o uno stack esplicito.
Che cos’è Ricerca in profondità DFS?
DFS usa ricorsione o uno stack esplicito.
Segue un percorso prima del backtracking.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Visualizzatore di Ricerca in profondità DFS in Python
O(V+E)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))Output previsto
['A', 'B', 'D', 'C', 'E']Come funziona
Ogni vertice e arco viene elaborato al massimo una volta: O(V+E).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.