Algoritmo di Ricerca in Profondità (DFS)
Immagina di controllare un robot posizionato in un determinato punto di un grafo con
n vertici e e archi. Vorresti partire da un vertice e, a poco a poco, attraversare l’intero grafo visitando tutti i vertici raggiungibili dal punto di partenza. L’algoritmo DFS ti permette di fare proprio questo: parte da un certo vertice, esplora un percorso finché non ci sono più vertici su quella strada, poi torna indietro ai nodi precedenti per esplorare qualunque altro percorso disponibile.
Un buon modo per pensare all’algoritmo DFS è l’idea di un robot che esplora il grafo e può vedere soltanto i vicini del nodo corrente e tutti i nodi che ha già visitato (il robot tiene traccia dell’intero percorso). Si tratta di un processo ricorsivo in cui, a ogni iterazione, il robot si sposta verso un nuovo vertice non ancora esplorato e ripete il procedimento finché non trova più vertici su quel cammino. Tenere a mente l’analogia di un piccolo robot che esplora il grafo aiuta molto nell’implementazione.
L’implementazione del DFS può essere realizzata con un algoritmo ricorsivo in cui teniamo traccia del vertice corrente (che indicheremo con
v) e di tutti i vertici già visitati (indicati come used):import sys
sys.setrecursionlimit(10 ** 6) # Aumenta il limite di ricorsione per consentire l'esecuzione corretta del DFS
n, e = map(int, input().split()) # n: vertici, e: archi
g = [[] for _ in range(n)] # grafo - lista di adiacenza
used = [False] * n # vertici usati (visitati)
for _ in range(e): # leggi le connessioni
a, b = map(int, input().split()) # a -> b e b -> a
g[a].append(b)
g[b].append(a)
def dfs(v): # ricerca in profondità
used[v] = True # segna il vertice come visitato
print(v, end=' ') # stampa il vertice
for to in g[v]: # per ogni vertice connesso a v
if not used[to]: # se il vertice non è ancora visitato
dfs(to) # chiama dfs su quel vertice
start = int(input()) # vertice di partenza
dfs(start) # chiama dfs sul vertice di partenzaQui inizializziamo il grafo e avviamo l’attraversamento a partire dal vertice
start. Inizialmente, tutti i valori di used sono False. Dopo aver visitato ogni vertice, lo segniamo come used[v] = True (significa che ora è visitato) e passiamo a esplorare i vicini del vertice corrente v.Osserva come la ricorsione agisce da esplorazione del percorso e poi permette di tornare indietro al nodo precedente per continuare a visitare i rimanenti vicini di quel vertice. Quando torniamo indietro dalla ricorsione, in pratica ci spostiamo nuovamente al vertice precedente.
Proviamo ora a simulare l’algoritmo su alcuni input:
n = 4, e = 4
I valori in input
a, b sono: [(0, 1), (0, 2), (1, 2), (3, 2)]Il vertice di partenza è 3
v = 3→used = [False, False, False, True]
- esamina tutti i vicini di 3 ⇒
[2]
v = 2→used = [False, False, True, True]
- esamina tutti i vicini di 2 ⇒
[0, 1]
v = 0→used = [True, False, True, True]
- esamina tutti i vicini di 0 ⇒
[1, 2]
v = 1→used = [True, True, True, True]
- esamina tutti i vicini di 1 ⇒
[0, 2]⇒ Tutti già visitati
- torna indietro da 1
- torna indietro da 0
- torna indietro da 2
- torna indietro da 3 → fine del DFS
- Fatto
n = 5, e = 4
I valori in input
a, b sono: [(0, 1), (0, 2), (1, 2), (3, 4)]Il vertice di partenza è 0
v = 0→used = [True, False, False, False, False]
- esamina tutti i vicini di 0 ⇒
[1, 2]
v = 1→used = [True, True, False, False, False]
- esamina tutti i vicini di 1 ⇒
[0, 2]
v = 2→used = [True, True, True, False, False]
- esamina tutti i vicini di 2 ⇒
[0, 1]⇒ Tutti già visitati
- torna indietro da 2
- torna indietro da 1
- torna indietro da 0 → fine del DFS
- Fatto
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
n = 10, e = 11 (esempio dal video)
I valori in input
a, b sono: [(0, 1), (0, 2), (1, 2), (1, 4), (1, 3), (3, 5), (6, 5), (5, 8), (5, 7), (7, 8), (8, 9)]Il vertice di partenza è 0
v = 0→used = [T, F, F, F, F, F, F, F, F, F]⇒ esamina[1, 2]
v = 1→used = [T, T, F, F, F, F, F, F, F, F]⇒ esamina[0, 2, 3, 4]
v = 2→used = [T, T, T, F, F, F, F, F, F, F]⇒ esamina[0, 1]
- torna indietro da 2
v = 1→used = [T, T, T, F, F, F, F, F, F, F]⇒ esamina[x, x, 3, 4]
v = 3→used = [T, T, T, T, F, F, F, F, F, F]⇒ esamina[1, 5]
v = 5→used = [T, T, T, T, F, T, F, F, F, F]⇒ esamina[3, 6, 7, 8]
v = 6→used = [T, T, T, T, F, T, T, F, F, F]⇒ esamina[5]
- torna indietro da 6
v = 7→used = [T, T, T, T, F, T, T, T, F, F]⇒ esamina[5, 8]
v = 8→used = [T, T, T, T, F, T, T, T, T, F]⇒ esamina[5, 7, 9]
v = 9→used = [T, T, T, T, F, T, T, T, T, T]⇒ esamina[8]
- torna indietro da 8
- torna indietro da 7
- torna indietro da 6
- torna indietro da 5
- torna indietro da 3
v = 1→used = [T, T, T, T, F, T, T, T, T, T]⇒ esamina[x, x, x, 4]
v = 4→used = [T, T, T, T, T, T, T, T, T, T]⇒ esamina[1]
- torna indietro da 4
- torna indietro da 1
- torna indietro da 0
- Fatto
Sfida: Calcolare il numero di componenti connesse in un grafo
Dato un grafo non orientato con
v vertici e e archi, si chiede di calcolare il numero di componenti connesse nel grafo. Un insieme di vertici si considera una componente connessa se è possibile raggiungere qualunque vertice di quell’insieme partendo da un altro vertice dello stesso insieme.Ingresso
La prima riga dell’ingresso contiene due interi
v (1 ≤ v ≤ 100 000) ed e (1 ≤ e ≤ 100 000).Le successive
e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v) che indicano che il vertice v1 è collegato al vertice v2 e viceversa.Uscita
Il programma deve stampare il numero di componenti connesse nel grafo.
Esempi
Ingresso | Uscita |
7 6
1 2
2 3
1 3
4 5
5 6
4 6 | 3 |
2 1
1 2 | 1 |
2 0 | 2 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB