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