BFS ট্রাভার্সাল এবং প্যারেন্ট ট্র্যাকিং ব্যবহার করে অনির্দেশিত গ্রাফে সাইকেল আছে কিনা চেক করা হয়।
উদাহরণ
from collections import deque
def has_cycle_bfs(V, edges):
adj = [[] for _ in range(V)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * V
parent = [-1] * V
for start in range(V):
if not visited[start]:
queue = deque([start])
visited[start] = True
while queue:
u = queue.popleft()
for v in adj[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
queue.append(v)
elif parent[u] != v:
return True # সাইকেল পাওয়া গেল
return False
V = 5
edges = [(0,1), (1,2), (2,0), (2,3), (2,1)]
print("ভার্টেক্স:", V)
print("এজ:", edges)
print("সাইকেল আছে?", "হ্যাঁ" if has_cycle_bfs(V, edges) else "না")
আউটপুট
ভার্টেক্স: 5 এজ: [(0, 1), (1, 2), (2, 0), (2, 3), (2, 1)] সাইকেল আছে? হ্যাঁ
ব্যাখ্যা
BFS ট্রাভার্সালের সময় প্যারেন্ট অ্যারে মেইনটেইন করা হয়।
ভিজিটেড নেইবর যদি প্যারেন্ট না হয়, তবে সাইকেল আছে (ব্যাক এজ)।
ডিসকানেক্টেড গ্রাফের জন্য সব ভার্টেক্স থেকে BFS চালানো হয়।
টাইম কমপ্লেক্সিটি: O(V + E)۔
