Chương trình Python tìm các đỉnh erreichable từ một đỉnh bằng BFS

Dùng BFS từ mỗi đỉnh trong list truy vấn để tìm tất cả đỉnh đạt được (cùng thành phần liên thông).

Ví dụ

from collections import deque

V = 7
adj = [[] for _ in range(V + 1)]
visited = [0] * (V + 1)

def add_edge(u, v):
    adj[u].append(v)
    adj[v].append(u)

def bfs_reachable(src):
    q = deque([src])
    visited[src] = 1
    reach = []
    while q:
        u = q.popleft()
        reach.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = 1
                q.append(v)
    return reach

def find_reachable(nodes):
    global visited
    for u in nodes:
        if not visited[u]:
            reach = bfs_reachable(u)
            print(f"Từ {u} đạt được:", reach)

# Xây đồ thị
add_edge(1, 2)
add_edge(2, 3)
add_edge(3, 4)
add_edge(3, 1)
add_edge(5, 6)
add_edge(5, 7)

queries = [2, 4, 5, 7]
find_reachable(queries)

Kết quả

Từ 2 đạt được: [2, 1, 3, 4]
Từ 4 đạt được: [2, 1, 3, 4]
Từ 5 đạt được: [5, 6, 7]
Từ 7 đạt được: [5, 6, 7]

Giải thích

• Đồ thị 2 thành phần liên thông: {1,2,3,4} và {5,6,7}.
• BFS từ 2 và 4 cho cùng thành phần; 5 và 7 cho thành phần kia.
• Mảng visited toàn cục tránh lặp lại BFS cho cùng thành phần.
• In ra các đỉnh đạt được theo thứ tự BFS.