Duyệt sâu trước để tìm đường và nhóm liên thông

Minh vẽ sơ đồ sáu phòng của thư viện. Phòng 1 nối phòng 2 và 3, phòng 2 nối phòng 4, còn phòng 5 nối phòng 6. Minh muốn biết từ phòng 1 có thể đến phòng 4 không và toàn bộ thư viện có bao nhiêu nhóm phòng tách biệt. Một cách là đi theo từng lối, đánh dấu nơi đã tới và quay lại khi hết đường mới.

Đi sâu theo một nhánh rồi quay lại

Duyệt sâu trước (depth-first search, DFS) chọn một hàng xóm chưa thăm, tiếp tục từ hàng xóm ấy, rồi quay lại khi không còn lựa chọn mới. Một phòng là một đỉnh (vertex); lối nối hai phòng là một cạnh (edge). Khi hai phòng đi qua lại được, ta dùng cạnh vô hướng.

Nếu xét hàng xóm tăng dần, từ 1 ta đi 2 rồi 4. Tại 4 không còn phòng mới, ta quay về 2 rồi 1 và xét 3. Nhóm còn lại gồm 5 và 6; bắt đầu từ 1 không thể đến đó. Một đỉnh không có cạnh cũng là một nhóm riêng.

Danh sách kề ghi các hàng xóm của từng đỉnh. Với cạnh vô hướng u v, phải thêm v vào g[u] và thêm u vào g[v]:

n = 6
edges = [(1, 2), (1, 3), (2, 4), (5, 6)]
g = [[] for _ in range(n + 1)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
for u in range(1, n + 1):
    print(u, g[u])

1 [2, 3]
2 [1, 4]
3 [1]
4 [2]
5 [6]
6 [5]

Chỉ số 0 không đại diện cho phòng nào trong ví dụ này. Với cạnh có hướng từ u đến v, chỉ thêm v vào g[u]. Lối ngược chỉ tồn tại nếu dữ liệu cũng cho cạnh ngược.

Đánh dấu khi đưa đỉnh vào ngăn xếp

Ngăn xếp (stack) lấy phần tử được đưa vào sau cùng trước. Trong Python, append đưa vào cuối và pop lấy ở cuối. Ta dùng visited[u] để ghi đỉnh đã được phát hiện, kể cả khi nó còn chờ trong ngăn xếp.

stack = [1]
stack.append(2)
stack.append(3)
print(stack.pop())
print(stack.pop())
print(stack)

3
2
[1]

Đánh dấu ngay khi đưa vào giúp mỗi đỉnh vào ngăn xếp nhiều nhất một lần. Điều này ngăn chu trình làm thuật toán quay vòng, đồng thời tránh nhiều bản sao đang chờ. Hình dưới ghi các đỉnh trong ngăn xếp từ đáy tới đỉnh; phần tử bên phải được lấy trước.

Ví dụ sau dùng reversed để trên cây này, hàng xóm nhỏ hơn được lấy ra trước. Mảng seen lưu tập phòng đã phát hiện; danh sách order lưu thứ tự được xử lý.

Sau khi lấy 1, chương trình đưa 3 rồi 2 vào ngăn xếp. Hai phòng này được đánh dấu ngay dù chưa được lấy ra. Sau đó 2 được lấy trước và phát hiện 4; phòng 1 đã có dấu nên không được đưa vào lần nữa. Khi 4 được xử lý xong, chương trình trở lại phòng 3 còn đang chờ. Thứ tự này phụ thuộc vào thứ tự các hàng xóm trong dữ liệu.

g = [[], [2, 3], [1, 4], [1], [2], [6], [5]]
seen = [False] * len(g)
stack = [1]
seen[1] = True
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in reversed(g[u]):
        if not seen[v]:
            seen[v] = True
            stack.append(v)
print(*order)
print("Đến phòng 4:", seen[4])
print("Đến phòng 6:", seen[6])

1 2 4 3
Đến phòng 4: True
Đến phòng 6: False

Tại mọi thời điểm, mỗi phòng được đánh dấu đều có đường đi từ phòng xuất phát. Khi xử lý một phòng đã đánh dấu, ta chỉ đánh dấu hàng xóm nối trực tiếp với nó. Khi ngăn xếp rỗng, không còn cạnh từ một phòng đã tới sang phòng chưa đánh dấu. Vì vậy mọi phòng có đường đi từ nguồn đều đã được tìm thấy.

Với n đỉnh, m cạnh vô hướng, danh sách kề chứa 2m lượt hàng xóm. Mỗi đỉnh vào ngăn xếp nhiều nhất một lần và mỗi lượt hàng xóm được xét nhiều nhất một lần. Thời gian là O(n + m), kể cả tạo mảng đánh dấu. Đồ thị chiếm O(n + m) bộ nhớ, còn ngăn xếp và mảng đánh dấu chiếm O(n). Với 50 000 đỉnh và 100 000 cạnh, có không quá 200 000 lượt xét hàng xóm.

Thứ tự DFS phụ thuộc cách quản lý hàng xóm

Xét các cạnh 1–2, 1–3 và 2–3, với hàng xóm theo thứ tự tăng dần. DFS đệ quy đi 1, rồi 2, rồi 3. Nếu đánh dấu cả 3 và 2 khi xử lý 1, đỉnh 3 đã có người phát hiện trước khi xử lý 2. Trên đồ thị khác, điều đó có thể thay đổi cả cha lẫn thứ tự so với đệ quy.

Để bắt chước thứ tự đệ quy, một cách là chỉ đánh dấu khi lấy ra. Mỗi lần lấy một đỉnh chưa thăm, ta xử lý đỉnh đó và đưa hàng xóm vào theo thứ tự ngược. Các bản sao đã thăm được bỏ qua. Lưu ý ngăn xếp có thể chứa nhiều bản sao, nên phần bộ nhớ phụ có thể lên tới O(n + m).

g = [[], [2, 3], [1, 3, 4], [1, 2, 5], [2], [3]]
def walk(mark_on_push):
    seen = [False] * len(g)
    stack = [1]
    seen[1] = mark_on_push
    order = []
    while stack:
        u = stack.pop()
        if not mark_on_push:
            if seen[u]:
                continue
            seen[u] = True
        order.append(u)
        for v in reversed(g[u]):
            if not seen[v]:
                if mark_on_push:
                    seen[v] = True
                stack.append(v)
    return order
print("Đánh dấu khi đưa vào:", walk(True))
print("Đánh dấu khi lấy ra:", walk(False))

Đánh dấu khi đưa vào: [1, 2, 4, 3, 5]
Đánh dấu khi lấy ra: [1, 2, 3, 5, 4]

Nếu hàng xóm chưa được sắp, reversed(g[u]) chỉ đảo thứ tự nhập, không tự sắp xếp. Khi đề quy định hàng xóm nhỏ trước, hãy gọi sort() trên từng danh sách kề. Chi phí sắp xếp cộng thêm, tối đa O(m log m) cho toàn bộ danh sách kề.

Truy lại một đường đi từ các đỉnh đã phát hiện

Khi phát hiện v từ u, lưu parent[v] = u. Mỗi liên kết cha là một cạnh thật; lần theo các liên kết từ đích về nguồn rồi đảo ngược sẽ cho một đường đi hợp lệ. Đỉnh nguồn có cha bằng 0 để đánh dấu điểm dừng.

g = [[], [2, 3], [1, 4], [1], [2], []]
def path(start, target):
    parent = [-1] * len(g)
    parent[start] = 0
    stack = [start]
    while stack and parent[target] == -1:
        u = stack.pop()
        for v in g[u]:
            if parent[v] == -1:
                parent[v] = u
                stack.append(v)
    if parent[target] == -1:
        return []
    route = []
    u = target
    while u != 0:
        route.append(u)
        u = parent[u]
    return route[::-1]
print(path(1, 4))
print(path(1, 1))
print(path(1, 5))

[1, 2, 4]
[1]
[]

Điều kiện đích bằng nguồn được xử lý ngay: đường đi chỉ có một đỉnh. Nếu đích không được đánh dấu, kết quả rỗng báo không có đường. Vì mỗi đỉnh chỉ được nhận cha một lần, truy ngược không bị vòng.

Đường tìm được không nhất thiết ít cạnh nhất. Chẳng hạn đồ thị có cạnh 1–2, 2–3, 3–4 và 1–4. Một DFS có thể đi qua 2 và 3 trước khi gặp 4, dù cạnh trực tiếp 1–4 ngắn hơn. Nếu cần số cạnh ít nhất trên đồ thị không trọng số, dùng BFS ở Bài 38.

g = [[], [2, 4], [1, 3], [2, 4], [1, 3]]
stack = [(1, [1])]
seen = set()
while stack:
    u, route = stack.pop()
    if u in seen:
        continue
    seen.add(u)
    if u == 4:
        print(route)
        break
    for v in reversed(g[u]):
        if v not in seen:
            stack.append((v, route + [v]))
print("Cạnh trực tiếp:", [1, 4])

[1, 2, 3, 4]
Cạnh trực tiếp: [1, 4]

Ví dụ trên sao chép đường đi để minh họa; với đồ thị lớn, lưu parent tiết kiệm bộ nhớ hơn. Tìm đường bằng danh sách kề mất O(n + m) thời gian và O(n) bộ nhớ phụ khi đánh dấu lúc đưa vào.

Mỗi lần bắt đầu từ đỉnh chưa thăm tìm được một thành phần

Trong đồ thị vô hướng, thành phần liên thông (connected component) là nhóm lớn nhất mà mọi cặp đỉnh trong nhóm đều đi tới nhau. Duyệt từ một đỉnh sẽ tìm đúng nhóm chứa nó. Sau đó duyệt tiếp từ đỉnh chưa thăm để tìm nhóm khác.

n = 6
edges = [(1, 2), (2, 3), (4, 5)]
g = [[] for _ in range(n + 1)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
seen = [False] * (n + 1)
sizes = []
for start in range(1, n + 1):
    if seen[start]:
        continue
    seen[start] = True
    stack = [start]
    size = 0
    while stack:
        u = stack.pop()
        size += 1
        for v in g[u]:
            if not seen[v]:
                seen[v] = True
                stack.append(v)
    sizes.append(size)
print("Số nhóm:", len(sizes))
print("Kích thước:", sizes)

Số nhóm: 3
Kích thước: [3, 2, 1]

Mỗi lần bắt đầu, đỉnh mới không thuộc nhóm nào đã tìm. DFS không thể đi sang nhóm khác vì không có cạnh nối hai nhóm. Sau vòng ngoài, mọi đỉnh đã thăm nên không nhóm nào bị bỏ sót. Tổng thời gian vẫn là O(n + m), không phải O(n × (n + m)), vì các lần duyệt dùng chung seen.

Với đồ thị có hướng, cách chia này phụ thuộc thứ tự bắt đầu và không tính thành phần liên thông mạnh. Khả năng đi từ A tới B cũng không đảm bảo đi ngược lại. Hãy đọc kỹ đề trước khi dùng khái niệm nhóm cho cạnh có hướng.

Giả sử cần tìm các trạm vừa đi tới được từ trạm 1, vừa có đường trở về trạm 1. Hãy duyệt từ 1 trên các cung ban đầu để tìm tập thứ nhất. Đảo chiều tất cả cung rồi duyệt từ 1 lần nữa để tìm tập thứ hai. Một đường từ trạm v về 1 trở thành đường từ 1 tới v sau khi đảo, nên giao hai tập chính là đáp án.

5 5 1
1 2
2 3
3 1
3 4
5 1

import sys
data = list(map(int, sys.stdin.read().split()))
n, m, start = data[:3]
g = [[] for _ in range(n + 1)]
reverse = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[3 + 2*i:5 + 2*i]
    g[u].append(v)
    reverse[v].append(u)
def reach(graph):
    seen = [False] * (n + 1)
    seen[start] = True
    stack = [start]
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if not seen[v]:
                seen[v] = True
                stack.append(v)
    return seen
forward = reach(g)
backward = reach(reverse)
print(sum(forward[i] and backward[i] for i in range(1, n + 1)))

3

Trạm 4 chỉ đi tới được từ 1, còn trạm 5 chỉ có đường đến 1. Cả hai không nằm trong giao. Hai đồ thị và hai lần duyệt đều dùng O(n + m) thời gian và bộ nhớ. Với 5000 trạm, 10 000 cung, mỗi lần duyệt xét nhiều nhất 10 000 lượt kề.

Một ô lưới có thể xem là một đỉnh

Một bản đồ gồm các ô trống . và tường #. Hai ô trống thuộc cùng vùng nếu đi được qua các ô trống bằng bốn hướng trên, dưới, trái, phải. Các ô chéo góc không nối trực tiếp.

Ta không cần tạo danh sách kề tường minh. Từ ô (r, c), thử bốn cặp độ lệch và kiểm tra biên trước khi truy cập ô mới. Dưới đây, seen[r][c] cho biết ô đã được đưa vào ngăn xếp.

grid = ["..#.", ".##.", "..#."]
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
sizes = []
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "#" or seen[r][c]:
            continue
        stack = [(r, c)]
        seen[r][c] = True
        size = 0
        while stack:
            x, y = stack.pop()
            size += 1
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols:
                    if grid[nx][ny] == "." and not seen[nx][ny]:
                        seen[nx][ny] = True
                        stack.append((nx, ny))
        sizes.append(size)
print("Số vùng:", len(sizes))
print("Diện tích:", sizes)

Số vùng: 2
Diện tích: [5, 3]

Nếu mọi ô đều là tường, vòng ngoài không bắt đầu lần duyệt nào và số vùng là 0. Với R hàng và C cột, mỗi ô được xét tối đa một lần và có bốn hướng cố định. Thời gian và bộ nhớ phụ là O(R × C). Lưới 100 × 100 có 10 000 ô và tối đa 40 000 lần thử hướng.

Nếu muốn tìm các ô đi tới được từ bất kỳ ô trống nào ở biên, hãy đưa tất cả những ô biên đó vào ngăn xếp ngay từ đầu. Đây là DFS nhiều nguồn (multiple-source). Đánh dấu ngay khi đưa vào để một ô góc không bị thêm hai lần. Những ô trống còn chưa đánh dấu sau khi duyệt là các ô bị tường bao kín:

grid = ["#####", "#..##", "##.##", "###.#"]
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
stack = []
for r in range(rows):
    for c in range(cols):
        if (r in (0, rows - 1) or c in (0, cols - 1)) and grid[r][c] == ".":
            seen[r][c] = True
            stack.append((r, c))
while stack:
    r, c = stack.pop()
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            if grid[nr][nc] == "." and not seen[nr][nc]:
                seen[nr][nc] = True
                stack.append((nr, nc))
print(sum(grid[r][c] == "." and not seen[r][c]
          for r in range(rows) for c in range(cols)))

3

Ô ở hàng cuối đi tới biên ngay; ba ô ở giữa chỉ chạm nó theo đường chéo nên vẫn bị bao kín. Mỗi ô được đánh dấu nhiều nhất một lần, vì vậy thời gian và bộ nhớ vẫn là O(R × C).

Đệ quy ngắn gọn nhưng đường dài có thể vượt giới hạn

DFS đệ quy dùng ngăn xếp lời gọi của Python thay cho ngăn xếp tự quản. Mỗi lời gọi giữ chỗ để quay về sau khi duyệt một nhánh. Một đường thẳng rất dài tạo rất nhiều lời gọi đang chờ.

g = [[], [2, 3], [1, 4], [1], [2]]
seen = [False] * len(g)
def dfs(u):
    seen[u] = True
    print(u)
    for v in g[u]:
        if not seen[v]:
            dfs(v)
dfs(1)

1
2
4
3

Ví dụ sau đặt giới hạn thấp để nhìn thấy lỗi trên một đường thẳng 200 đỉnh. Chương trình chủ động bắt RecursionError để hiển thị kết quả minh họa.

import sys
sys.setrecursionlimit(100)
def visit(u):
    if u < 200:
        visit(u + 1)
try:
    visit(1)
except RecursionError:
    print("Vượt giới hạn độ sâu đệ quy")

Vượt giới hạn độ sâu đệ quy

Tăng giới hạn đệ quy không làm bộ nhớ vô hạn. Với dữ liệu lớn hoặc đường đi có thể dài, ngăn xếp tường minh thường an toàn hơn. Hãy kiểm tra ràng buộc và môi trường chạy trước khi chọn cách cài đặt.

Lỗi thường gặp

Tóm tắt

• DFS đi sâu theo nhánh; ngăn xếp giúp chủ động quản lý các đỉnh đang chờ.
• Đánh dấu khi đưa vào giúp mỗi đỉnh vào ngăn xếp một lần và đủ để tìm khả năng đi tới.
• Duyệt từ mọi đỉnh chưa thăm tìm các thành phần của đồ thị vô hướng.
• Với danh sách kề, tổng chi phí duyệt là O(n + m); trên lưới bốn hướng là O(R × C).
• Muốn thứ tự giống đệ quy, phải quản lý thứ tự hàng xóm và thời điểm đánh dấu phù hợp.

Kiểm tra nhanh

Đọc thêm

• Depth First Search — CP-Algorithms
• Giới hạn đệ quy của Python