Chương trình Python phát hiện chu trình đồ thị vô hướng bằng BFS

Dùng BFS với queue và mảng parent để phát hiện chu trình trong đồ thị vô hướng (có thể không liên thông).

Ví dụ

from collections import deque

def add_edge(adj, u, v):
    adj[u].append(v)
    adj[v].append(u)

def has_cycle_bfs(adj, start, V, visited):
    parent = [-1] * V
    q = deque([start])
    visited[start] = True

    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                q.append(v)
            elif parent[u] != v:
                return True
    return False

def is_cyclic(adj, V):
    visited = [False] * V
    for i in range(V):
        if not visited[i] and has_cycle_bfs(adj, i, V, visited):
            return True
    return False

V = 5
adj = [[] for _ in range(V)]
edges = [(0,1), (1,2), (2,0), (2,3), (2,1)]
for u,v in edges:
    add_edge(adj, u, v)

print("Có chu trình?", "Có" if is_cyclic(adj, V) else "Không")

Kết quả

Có chu trình? Có

Giải thích

• BFS từ mỗi đỉnh chưa thăm (xử lý đồ thị không liên thông).
• Mảng parent lưu cha của mỗi đỉnh trong cây BFS.
• Gặp đỉnh đã thăm mà không phải cha -> có chu trình.
• Độ phức tạp O(V+E).