BFS ট্রাভার্সাল ব্যবহার করে নির্দিষ্ট সোর্স নোড থেকে পৌঁছানো যাবলে সব নোড (রিচেয়াবল নোড) খুঁজে বের করা হয়।
উদাহরণ
from collections import deque
def bfs_reachable(adj, start):
visited = [False] * len(adj)
queue = deque([start])
visited[start] = True
reachable = []
while queue:
u = queue.popleft()
reachable.append(u)
for v in adj[u]:
if not visited[v]:
visited[v] = True
queue.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:
adj[u].append(v)
adj[v].append(u)
queries = [2, 4, 5, 7]
for q in queries:
print(f"নোড {q} থেকে রিচেয়াবল: {bfs_reachable(adj, q)}")
আউটপুট
নোড 2 থেকে রিচেয়াবল: [2, 1, 3, 4] নোড 4 থেকে রিচেয়াবল: [4, 3, 1, 2] নোড 5 থেকে রিচেয়াবল: [5, 6, 7] নোড 7 থেকে রিচেয়াবল: [7, 5, 6]
ব্যাখ্যা
BFS লেভেল-বাই-লেভেল এক্সপ্লোর করে।
ভিজিটেড অ্যারে দিয়ে রিপিট ভিজিট এড়ানো হয়।
কানেক্টেড কম্পোনেন্টের সব নোড রিচেয়াবল।
ডিসকানেক্টেড কম্পোনেন্টের নোড পাওয়া যায় না।
