Rilevamento di cicli in un grafo
Individuare i cicli nei grafi è essenziale per comprendere la struttura e le proprietà dei dati in molti ambiti, come la gestione delle dipendenze, il rilevamento di deadlock e il routing di rete. Riconoscendo la presenza di cicli, è possibile evitare problemi come dipendenze circolari, inefficienze e persino blocchi di sistema.
Una versione modificata di DFS può essere utilizzata per verificare l’esistenza di un ciclo in un grafo.
Durante l’attraversamento di un grafo con DFS, di solito si contrassegnano i vertici come visitati/utilizzati o non visitati. Per individuare i cicli, però, questo non basta. È necessario mantenere 3 stati per ciascun vertice:
- Vertice non visitato
- Vertice e relativi sotto-nodi DFS in corso di elaborazione
- Vertice completamente visitato (insieme ai suoi nodi figli)
In questo modo si può rilevare la presenza di un ciclo se, durante l’attraversamento, si raggiunge un vertice che è attualmente in elaborazione.
➰
Se, durante l’attraversamento, raggiungiamo un vertice contrassegnato come in elaborazione (2), significa che abbiamo trovato un ciclo.
L’algoritmo esegue i seguenti passaggi:
- Contrassegnare tutti i vertici come non visitati
- Avviare una DFS da un vertice qualsiasi
- Per il vertice corrente, contrassegnarlo come in elaborazione
- Al termine dell’elaborazione di tutti i figli del vertice corrente, contrassegnarlo come completamente visitato
L’algoritmo può essere applicato sia a grafi diretti che a grafi indiretti:
color = [1] * n # colore dei vertici (1: non visitato, 2: in elaborazione, 3: completamente visitato)
def dfs(v, p): # depth-first search (v: vertice, p: genitore)
color[v] = 2 # contrassegna il vertice come in elaborazione
cycle = False # flag per verificare se è presente un ciclo
for to in g[v]: # per ogni vertice collegato a v
if color[to] == 1: # se il vertice non è visitato
cycle |= dfs(to, v) # chiama la dfs sul vertice 'to' e aggiorna il flag se c'è un ciclo
elif color[to] == 2 and to != p: # se il vertice è in elaborazione e non è il genitore
cycle = True # imposta il flag a True
color[v] = 3 # contrassegna il vertice come completamente visitato
return cycle # restituisce il flag
for start in range(n): # per ogni vertice
if color[start] == 1: # se il vertice non è visitato
if dfs(start, -1): # chiama dfs sul vertice e verifica se è presente un ciclo
print('Cycle') # stampa "Cycle"
break # interrompe il ciclo
else: # se il ciclo non è stato interrotto con break
print('No cycle') # stampa "No cycle"Nota che per i grafi diretti non è necessario considerare il vertice genitore. Sai spiegare il perché 🤔?
Vediamo come l’algoritmo si comporta con diversi input:
n = 4, e = 4
Le coppie di input
a, b sono: [(0, 1), (0, 2), (1, 2), (3, 2)]Il vertice di partenza è 3
v=3, p=-1→color = [1, 1, 1, 2]⇒ esamina i vicini di 3 ⇒[2]
v=2, p=3→color = [1, 1, 2, 2]⇒ esamina i vicini di 2 ⇒[0, 1]
v=0, p=2→color = [2, 1, 2, 2]⇒ esamina i vicini di 0 ⇒[1, 2]
v=1, p=0→color = [2, 2, 2, 2]⇒ esamina i vicini di 1 ⇒[0, 2]⇒ 0 è contrassegnato come 1 ⇒ aggiornacycle = True⇒return True
Challenge: Verificare se un grafo contiene un ciclo
Dato un grafo diretto con
v vertici e e archi, si richiede di verificare se il grafo contiene un ciclo.Input
La prima riga di input 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 l’esistenza di un percorso dal vertice v1 al vertice v2.Output
Il programma deve stampare “Yes” se il grafo contiene un ciclo, altrimenti “No”.
Examples
Input | Output |
4 3
1 2
2 3
3 1
| Yes |
4 3
1 2
1 3
2 4 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB