ตรวจสอบว่า Undirected Graph มี Cycle หรือไม่ด้วย BFS ใน Python

ใช้ BFS ตรวจจับ Cycle ในกราฟไม่มีทิศทาง โดยติดตาม parent ของแต่ละโหนด ถ้าเจอเพื่อนบ้านที่เยี่ยมชมแล้วแต่ไม่ใช่ parent → มี Cycle

ตัวอย่างโค้ด

from collections import deque

def has_cycle_bfs(adj, V):
    visited = [False] * V
    for start in range(V):
        if not visited[start]:
            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

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

print("Graph has cycle:", has_cycle_bfs(adj, V))

ผลลัพธ์

Graph has cycle: True

คำอธิบาย

• ใช้ BFS จากทุกโหนดที่ยังไม่ได้เยี่ยม (กรณีกราฟไม่เชื่อมต่อ)

• เก็บ parent ของแต่ละโหนดใน BFS tree

• ถ้าเจอ neighbor ที่ visited แล้ว และไม่ใช่ parent → พบ back-edge → มี Cycle

• Time: O(V+E), Space: O(V)