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