Chương trình Python tìm thành phần liên thông bằng DFS đồ thị vô hướng

Triển khai đồ thị vô hướng với danh sách kề, dùng DFS đệ quy để tìm các thành phần liên thông.

Ví dụ

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, comp):
        visited[v] = True
        comp.append(v)
        for nei in self.adj[v]:
            if not visited[nei]:
                self.dfs_util(nei, visited, comp)

    def connected_components(self):
        visited = [False] * self.V
        comps = []
        for v in range(self.V):
            if not visited[v]:
                comp = []
                self.dfs_util(v, visited, comp)
                comps.append(comp)
        return comps

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("Thành phần liên thông:", g.connected_components())

Kết quả

1-0, 2-3, 3-0
Thành phần liên thông: [[0, 1, 3, 2], [4]]

Giải thích

• Lớp Graph lưu danh sách kề adj.
• add_edge thêm cạnh hai chiều.
• dfs_util đệ quy duyệt DFS, thu thập đỉnh vào comp.
• connected_components lặp qua mọi đỉnh chưa thăm, chạy DFS, gom thành phần.
• Kết quả: thành phần 1: {0,1,2,3}, thành phần 2: {4} (đỉnh cô lập).