Détection de cycles dans un graphe
La détection de cycles dans un graphe est primordiale pour comprendre la structure et les propriétés des données dans divers domaines, tels que la gestion des dépendances, la détection d’interblocages et le routage réseau. En identifiant les cycles, nous pouvons éviter des problèmes comme les dépendances circulaires, les inefficiences et même des pannes de système.
Une version modifiée de la DFS peut être utilisée pour détecter un cycle dans un graphe.
Lorsque l’on parcourt un graphe avec une DFS, on marque habituellement les sommets comme visités/utilisés ou non visités. Pour détecter des cycles, cela ne suffit pas. Il faut définir 3 états pour chaque sommet :
- Le sommet n’est pas visité
- Le sommet et son sous-arbre DFS sont en cours de traitement
- Le sommet est entièrement visité (avec tous ses nœuds enfants)
De cette façon, on peut repérer un cycle si l’on atteint un sommet qui est en cours de traitement pendant la traversée du graphe.
➰
Si, en parcourant le graphe, nous atteignons un sommet marqué comme étant en cours de traitement (2), alors nous avons découvert un cycle.
L’algorithme exécute les étapes suivantes :
- Marquer tous les sommets comme non visités
- Démarrer une DFS à partir d’un sommet quelconque
- Pour le sommet courant, le marquer comme en cours de traitement
- Lorsque tous les nœuds enfants du sommet courant ont été traités, le marquer comme entièrement visité
L’algorithme peut s’appliquer aussi bien aux graphes dirigés qu’aux graphes non dirigés :
color = [1] * n # couleur des sommets (1 : non visité, 2 : en cours de traitement, 3 : entièrement visité)
def dfs(v, p): # recherche en profondeur (v : sommet, p : parent)
color[v] = 2 # marquer le sommet comme en cours de traitement
cycle = False # indicateur pour vérifier la présence d'un cycle
for to in g[v]: # pour chaque sommet connecté à v
if color[to] == 1: # si le sommet n'est pas visité
cycle |= dfs(to, v) # appeler dfs sur ce sommet et noter s'il y a un cycle
elif color[to] == 2 and to != p: # si le sommet est en cours de traitement et qu'il ne s'agit pas du parent
cycle = True # marquer l'indicateur comme étant vrai
color[v] = 3 # marquer le sommet comme entièrement visité
return cycle # renvoyer l'indicateur
for start in range(n): # pour chaque sommet
if color[start] == 1: # si le sommet n'est pas visité
if dfs(start, -1): # appeler dfs sur ce sommet et vérifier l'existence d'un cycle
print('Cycle') # afficher cycle
break # interrompre la boucle
else: # si la boucle n'a pas été interrompue par un break
print('No cycle') # afficher no cycleNotez que pour les graphes dirigés, il n’est pas nécessaire de prendre en compte le sommet parent. Pouvez-vous expliquer pourquoi 🤔?
Simulons cet algorithme sur plusieurs exemples :
n = 4, e = 4
La liste des paires d’entrées
a, b est la suivante : [(0, 1), (0, 2), (1, 2), (3, 2)]Le sommet de départ est 3
v=3, p=-1→color = [1, 1, 1, 2]⇒ explorer tous les voisins de 3 ⇒[2]
v=2, p=3→color = [1, 1, 2, 2]⇒ explorer tous les voisins de 2 ⇒[0, 1]
v=0, p=2→color = [2, 1, 2, 2]⇒ explorer tous les voisins de 0 ⇒[1, 2]
v=1, p=0→color = [2, 2, 2, 2]⇒ explorer tous les voisins de 1 ⇒[0, 2]⇒ 0 est marqué comme 1 ⇒ marquercycle = True⇒return True
Défi : Vérifier si un graphe contient un cycle
Étant donné un graphe dirigé avec
v sommets et e arêtes, on vous demande de vérifier si le graphe contient un cycle.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 100 000) et e (1 ≤ e ≤ 100 000).Les
e lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v) indiquant qu’il existe un chemin du sommet v1 vers le sommet v2.Sortie
Le programme doit imprimer « Yes » si le graphe contient un cycle et « No » sinon.
Exemples
Entrée | Sortie |
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