Algoritmi di ricerca in profondità (DFS)

7.1 Principi di funzionamento dell'algoritmo DFS

Depth-First Search (DFS) è un algoritmo che permette di esplorare o cercare in un grafo. Inizia da un vertice iniziale e va in profondità nel grafo finché non raggiunge un vertice senza vicini non visitati, poi torna indietro e continua il processo con altri vertici.

Passi dell'algoritmo:

1. Iniziamo con il vertice iniziale scelto e lo segniamo come visitato.
2. Esploriamo il primo vertice vicino non visitato.
3. Ripetiamo i passi 1 e 2 per questo vertice vicino.
4. Se tutti i vicini del vertice corrente sono visitati, torniamo indietro al vertice precedente e continuiamo il processo.
5. Il processo si ripete fino a quando non sono visitati tutti i vertici raggiungibili dal vertice iniziale.

Visualizzazione:

Complessità temporale e spaziale di DFS:

Complessità temporale:

O(V + E), dove V è il numero di vertici, E è il numero di archi.

Ogni nodo e ogni arco del grafo sono visitati una volta.

Complessità spaziale:

O(V), dato che si usa lo stack delle chiamate o uno stack esplicito per memorizzare i vertici, e array per memorizzare lo stato (vertici visitati).

7.2 Implementazione DFS con ricorsione

Iniziamo con l'implementazione di DFS usando la ricorsione — il codice sarà bello e compatto.

Implementazione ricorsiva di DFS:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Elaborazione del nodo
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# Esempio di utilizzo:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Implementazione DFS con stack

Senza la ricorsione il codice sarà un po' più lungo, dato che abbiamo bisogno di memorizzare una lista di vertici visitati.

Implementazione iterativa di DFS (usando uno stack):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Elaborazione del nodo
        
            for neighbor in reversed(graph[vertex]):  # Ordine inverso per l'ordine corretto di esplorazione
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Esempio di utilizzo:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Esempi di problemi risolti con DFS

Esempi classici di problemi risolti con DFS:

1. Ricerca di un percorso in un labirinto:

Usato per trovare un percorso in un labirinto dal punto di partenza al punto finale.

Applicazioni:

Nei videogiochi e nella robotica per la navigazione nei labirinti e in spazi complessi.

2. Verifica della connettività di un grafo:

Verifica se un grafo è connesso (esiste un percorso tra qualsiasi coppia di vertici).

Applicazioni:

Nell'analisi di rete per verificare la connettività della rete.

3. Ordinamento topologico:

Usato per ordinare i vertici di un grafo aciclico diretto (DAG) in modo tale che per ogni arco (u, v) il vertice u preceda il vertice v.

Applicazioni:

Nei compilatori per ordinare dipendenze e compiti.

4. Rilevamento di cicli in un grafo:

Verifica se un grafo contiene cicli.

Applicazioni:

Nell'analisi delle dipendenze per rilevare dipendenze cicliche.

5. Generazione di labirinti:

Utilizzo di DFS per generare labirinti casuali.

Applicazioni:

Nei giochi e nelle applicazioni di intrattenimento per creare labirinti.