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

Tương tự DFS nhưng dùng BFS (queue) để 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 bfs_component(self, start, visited):
        from collections import deque
        q = deque([start])
        visited[start] = True
        comp = []
        while q:
            u = q.popleft()
            comp.append(u)
            for v in self.adj[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)
        return comp

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

g = Graph(6)
g.add_edge(1, 0)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(5, 0)
print("Thành phần liên thông:", g.connected_components())

Kết quả

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

Giải thích

• BFS dùng queue (deque) thay vì đệ quy.
• bfs_component trả về list đỉnh trong thành phần chứa start.
• Duyệt tất cả đỉnh, chạy BFS cho đỉnh chưa thăm.
• Kết quả: 2 thành phần: {0,1,5} và {2,3,4}.