หา Connected Components ทั้งหมดใน Undirected Graph ด้วย DFS ใน Python

เมื่อต้องการหา Connected Components ทั้งหมดในกราฟไม่มีทิศทาง ใช้ Depth First Search (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 neighbor in self.adj[v]:
            if not visited[neighbor]:
                self.dfs_util(neighbor, 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(5)
g.add_edge(1, 0)
g.add_edge(2, 3)
g.add_edge(3, 0)
print("Edges: 1-0, 2-3, 3-0")
print("Connected components:", g.connected_components())

ผลลัพธ์

Edges: 1-0, 2-3, 3-0
Connected components: [[0, 1, 3, 2], [4]]

คำอธิบาย

• คลาส Graph เก็บจำนวนโหนด V และ adjacency list

• add_edge เพิ่มขอบสองทิศทาง (undirected)

• dfs_util DFS แบบเรียกซ้ำ เก็บโหนดที่เยี่ยมชมใน component

• connected_components วนทุกโหนด ถ้ายังไม่ได้เยี่ยม เริ่ม DFS ใหม่

• โหนด 4 โดดเดี่ยว (isolated) → เป็น component เดียว