เมื่อต้องการหาโหนดทั้งหมดที่ถึงได้จากโหนดเริ่มต้นแต่ละตัวในลิสต์ ใช้ BFS จากแต่ละโหนดนั้น
ตัวอย่างโค้ด
from collections import deque
def add_edge(adj, u, v):
adj[u].append(v)
adj[v].append(u)
def bfs_reachable(adj, start):
visited = [False] * len(adj)
q = deque([start])
visited[start] = True
reachable = []
while q:
u = q.popleft()
reachable.append(u)
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
return reachable
V = 7
adj = [[] for _ in range(V + 1)]
edges = [(1,2), (2,3), (3,4), (3,1), (5,6), (5,7)]
for u, v in edges:
add_edge(adj, u, v)
queries = [2, 4, 5, 7]
for u in queries:
print(f"Reachable from {u}:", bfs_reachable(adj, u))ผลลัพธ์
Reachable from 2: [2, 1, 3, 4] Reachable from 4: [4, 3, 1, 2] Reachable from 5: [5, 6, 7] Reachable from 7: [7, 5, 6]
คำอธิบาย
กราฟมี 2 component: {1,2,3,4} และ {5,6,7}
BFS จาก 2 และ 4 ให้โหนดเดียวกัน (component เดียวกัน)
BFS จาก 5 และ 7 ให้โหนดเดียวกัน (component อีกอัน)
ใช้ visited array ใหม่สำหรับแต่ละ BFS เริ่มต้น
