Détection de cycles dans les graphes orientés et non orientés

Pourquoi la détection des cycles est importante

from collections import defaultdict

# Undirected cycle: A-B-C-A (triangle)
undirected = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
    undirected[u].append(v)
    undirected[v].append(u)

# Directed cycle: A->B->C->A
directed = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
    directed[u].append(v)  # one direction only

# Key difference:
# Undirected: edge A-B appears as both A->B and B->A
# Must track parent to distinguish cycle from back-edge to parent
print('Undirected and directed cycles need different detection')

Détection des cycles non orientés avec DFS

def has_cycle_undirected(n, edges):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                if dfs(nb, node):  # recurse with current as parent
                    return True
            elif nb != parent:     # visited and not parent = CYCLE
                return True
        return False

    for node in range(n):
        if node not in visited:
            if dfs(node, -1):  # -1 = no parent for root
                return True
    return False

print(has_cycle_undirected(4, [(0,1),(1,2),(2,3),(3,1)]))  # True
print(has_cycle_undirected(3, [(0,1),(1,2)]))               # False

Cycle non orienté avec BFS

from collections import deque, defaultdict

def has_cycle_bfs_undirected(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    for start in range(n):
        if start in visited:
            continue
        visited.add(start)
        parent = {start: -1}
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nb in graph[node]:
                if nb not in visited:
                    visited.add(nb)
                    parent[nb] = node
                    queue.append(nb)
                elif parent[node] != nb:  # visited and not parent = CYCLE
                    return True
    return False

print(has_cycle_bfs_undirected(4, [(0,1),(1,2),(2,0)]))  # True

Cycle orienté : pourquoi le suivi du parent échoue

# Three-state DFS coloring:
# WHITE (0): not yet visited
# GRAY  (1): currently being visited (in DFS stack)
# BLACK (2): fully visited (all descendants processed)

# Why parent fails for directed graphs:
# A -> C  (no cycle)
# B -> C  (no cycle)
# If we DFS from A, mark C gray
# Then DFS from B finds C is gray -- but this is NOT a cycle!
# C is gray from A's path, not B's path.
# Parent tracking only works when the back-edge goes to the IMMEDIATE parent.
print('Directed graph: use 3-state coloring (white/gray/black)')

Détection des cycles orientés avec un DFS à trois états

def has_cycle_directed(n, edges):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    state = [0] * n  # 0=white, 1=gray, 2=black

    def dfs(node):
        state[node] = 1  # mark gray (in stack)
        for nb in graph[node]:
            if state[nb] == 1:  # gray = back edge = CYCLE
                return True
            if state[nb] == 0:  # white = unvisited
                if dfs(nb):
                    return True
        state[node] = 2  # mark black (fully processed)
        return False

    for node in range(n):
        if state[node] == 0:
            if dfs(node):
                return True
    return False

print(has_cycle_directed(4, [(0,1),(1,2),(2,0),(2,3)]))  # True (0->1->2->0)
print(has_cycle_directed(3, [(0,1),(1,2)]))               # False

Ordonnancement des cours : cycle dans un DAG

from collections import defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)  # b is prerequisite for a: b -> a

    state = [0] * num_courses

    def dfs(course):
        if state[course] == 1: return False  # cycle!
        if state[course] == 2: return True   # already verified
        state[course] = 1  # mark as in-progress
        for next_course in graph[course]:
            if not dfs(next_course):
                return False
        state[course] = 2  # mark as done
        return True

    return all(dfs(i) for i in range(num_courses) if state[i] == 0)

print(can_finish(2, [[1,0]]))        # True: take 0 then 1
print(can_finish(2, [[1,0],[0,1]]))  # False: circular dependency

Détection des cycles avec l'algorithme de Kahn (BFS)

from collections import defaultdict, deque

def has_cycle_kahn(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    # Start with all zero in-degree nodes
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1
        for nb in graph[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0:
                queue.append(nb)

    return processed != n  # if not all processed, cycle exists

print(has_cycle_kahn(4, [(0,1),(1,2),(2,0),(2,3)]))  # True
print(has_cycle_kahn(3, [(0,1),(1,2)]))               # False

Trouver le cycle : collecte des nœuds du cycle

def find_cycle_nodes(n, edges):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    state = [0] * n
    path = []  # current DFS path
    cycle = []

    def dfs(node):
        state[node] = 1
        path.append(node)
        for nb in graph[node]:
            if state[nb] == 1:  # back edge -> found cycle
                start = path.index(nb)
                cycle.extend(path[start:])
                return True
            if state[nb] == 0 and dfs(nb):
                return True
        path.pop()
        state[node] = 2
        return False

    for i in range(n):
        if state[i] == 0 and dfs(i):
            break
    return cycle

print(find_cycle_nodes(4, [(0,1),(1,2),(2,0),(2,3)]))  # [0, 1, 2]

Trouver les états sûrs à terme

def eventual_safe_nodes(graph):
    n = len(graph)
    state = [0] * n  # 0=unvisited, 1=visiting, 2=safe

    def dfs(node):
        if state[node] == 1:  # currently visiting = cycle
            return False
        if state[node] == 2:  # already verified safe
            return True
        state[node] = 1  # mark as visiting
        for nb in graph[node]:
            if not dfs(nb):
                return False  # leads to cycle, not safe
        state[node] = 2  # mark as safe
        return True

    return [i for i in range(n) if dfs(i)]

# [[1,2],[2,3],[5],[0],[5],[],[]] means:
# 0->[1,2], 1->[2,3], 2->[5], 3->[0] (cycle!), 4->[5], 5->[], 6->[]
print(eventual_safe_nodes([[1,2],[2,3],[5],[0],[5],[],[]]))
# [2, 4, 5, 6]

Connexion redondante dans un graphe non orienté

def find_redundant_connection(edges):
    n = len(edges)
    parent = list(range(n + 1))
    rank = [0] * (n + 1)

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False  # already connected = cycle!
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]  # this edge creates the cycle
    return []

print(find_redundant_connection([[1,2],[1,3],[2,3]]))  # [2,3]
print(find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]]))  # [1,4]

Résumé : stratégies de détection des cycles

# Cycle detection summary:
# Graph type  | Algorithm            | Complexity
# ------------|----------------------|-----------
# Undirected  | DFS + parent track   | O(V + E)
# Undirected  | Union-Find (DSU)     | O(E * alpha(V))
# Directed    | DFS 3-state (W/G/B)  | O(V + E)
# Directed    | Kahn's BFS topo sort | O(V + E)

# When to choose:
# Online (edges added one at a time): Union-Find
# Need topological order too: Kahn's BFS
# Need cycle nodes identified: 3-state DFS with path stack
# Simple existence check: any of the above
print('Always clarify directed vs undirected before coding')

Vérification rapide

Récapitulatif de la leçon