ใช้ BFS หา Connected Components ทั้งหมดในกราฟไม่มีทิศทาง โดยเริ่ม BFS จากโหนดที่ยังไม่ได้เยี่ยมชมแต่ละตัว
ตัวอย่างโค้ด
from collections import deque
def bfs_components(adj, V):
visited = [False] * V
components = []
for start in range(V):
if not visited[start]:
comp = []
q = deque([start])
visited[start] = True
while q:
u = q.popleft()
comp.append(u)
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
components.append(comp)
return components
V = 6
adj = [[] for _ in range(V)]
edges = [(1,0), (2,3), (3,4), (5,0)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
print("Components:", bfs_components(adj, V))ผลลัพธ์
Components: [[0, 1, 5], [2, 3, 4]]
คำอธิบาย
สร้าง adjacency list จากขอบที่กำหนด
วนทุกโหนด ถ้ายังไม่ visited เริ่ม BFS ใหม่
BFS เก็บโหนดทั้งหมดที่ถึงได้ใน component นั้น
Component 1: 0-1-5, Component 2: 2-3-4
BFS ใช้ queue (deque) แทน recursion stack
