Find if Path Exists in Graph

Q: Độ phức tạp thời gian để tìm xem có đường đi trong đồ thị hay không là bao nhiêu?

BFS hoặc DFS cần thời gian và bộ nhớ O(n + m) với n nút và m cạnh. Cấu trúc union-find dùng phép hợp theo kích thước và rút ngắn đường đi cần thời gian O(n + m·α(n)) và bộ nhớ O(n) , còn α(n) là một hằng số nhỏ trong thực tế.

Q: Path compression và union by size có tác dụng gì trong union-find?

Chúng giữ cho cây có độ sâu thấp để find luôn chạy nhanh. Phép hợp nhất theo kích thước đặt cây nhỏ hơn bên dưới cây lớn hơn, vì vậy một nút chỉ sâu thêm khi nhóm của nó tăng ít nhất gấp đôi, nhờ đó độ sâu được giới hạn ở mức log n . Nén đường đi hoặc rút ngắn đường đi giúp đường đi đến gốc ngắn hơn mỗi khi chạy find .

DễĐồ thị Tập hợp rời rạc

+10

Một đồ thị vô hướng có n nút, được đánh số từ 0 đến n-1. Mỗi phần tử [u, v] trong edges nối các nút u và v, và bạn có thể đi qua cạnh theo cả hai hướng. Trả về true nếu bạn có thể đi từ source đến destination theo các cạnh, nếu không thì trả về false. Một nút luôn có thể đi đến chính nó.

Hàm

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

ninteger: số lượng nút
edgesinteger-2d-array: các cạnh, mỗi cạnh là một cặp [u, v] gồm hai nút được kết nối
sourceinteger: nút mà bạn bắt đầu từ đó
destinationinteger: nút bạn muốn đi tới
Trả vềboolean: liệu một đường dẫn nào đó có nối nguồn với đích hay không

Ràng buộc

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] với 0 ≤ u, v ≤ n-1 và u ≠ v
Không có cạnh nào xuất hiện hai lần, theo cả hai hướng.
0 ≤ source, destination ≤ n-1

Ví dụ

Đầu vào: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Đầu ra: true
Giải thích: Đường đi 0 → 1 → 2 → 3 sử dụng ba cạnh, vì vậy có thể đi đến nút 3. Nút 4 và 5 tạo thành một phần riêng mà đường đi không cần đến.

Đầu vào: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Đầu ra: false
Giải thích: Từ nút 2, bạn đi đến 0 rồi đến 1, không đến nút nào khác. Nút 4 chỉ nối với nút 3, và không có cạnh nào nối {0, 1, 2} với {3, 4}, nên đáp án là false.

Câu hỏi mở rộng

Giả sử các cạnh chỉ đi theo một chiều: [u, v] chỉ cho phép bạn đi từ u đến v. Cách nào trong ba cách tiếp cận vẫn hoạt động, và bạn cần thay đổi gì trong các cách đó?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Câu hỏi đặt ra là liệu source và destination có nằm trong cùng một thành phần liên thông của đồ thị hay không. Tìm kiếm theo chiều rộng trên danh sách kề sẽ trả lời câu hỏi này bằng cách duyệt qua mỗi nút và cạnh một lần. Cấu trúc dữ liệu hợp nhất-tìm kiếm trả lời câu hỏi này bằng cách gộp các nhóm khi đọc các cạnh, không cần danh sách nút kề.

Quét các cạnh cho đến khi không còn gì thay đổi

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Đánh dấu source là đã đến được rồi duyệt qua danh sách cạnh. Một cạnh có một đầu đã được đánh dấu thì đầu còn lại có thể đến được, vậy hãy đánh dấu đầu đó. Lặp lại cho đến khi một lượt duyệt không đánh dấu thêm nút nào hoặc destination được đánh dấu.

Nút cách source một khoảng k sẽ được đánh dấu muộn nhất ở lượt duyệt thứ k, và một nút chỉ được đánh dấu thông qua một cạnh nối với nút đã đánh dấu, nên đáp án chính xác. Chi phí phụ thuộc vào thứ tự các cạnh. Nếu một đường đi được liệt kê từ đầu xa trở về, mỗi lượt duyệt đánh dấu một nút: đường đi có 5000 cạnh cần 5000 lượt duyệt, với 2.5 × 10^7 lần kiểm tra cạnh.

Thuật toán

Tạo reached và chỉ đánh dấu source.
Duyệt qua mọi cạnh [u, v]. Nếu chỉ có đúng một đầu được đánh dấu, hãy đánh dấu đầu còn lại và ghi nhận rằng đã có thay đổi.
Lặp lại lượt duyệt khi vẫn còn thay đổi và destination chưa được đánh dấu.
Trả về việc destination có được đánh dấu hay không.

def validPath(n, edges, source, destination):
    reached = [False] * n
    reached[source] = True
    changed = True
    while changed and not reached[destination]:
        changed = False
        for u, v in edges:
            # An edge with exactly one reached end pulls the other end in.
            if reached[u] != reached[v]:
                reached[u] = reached[v] = True
                changed = True
    return reached[destination]

Tìm kiếm theo chiều rộng

Ý tưởng

Lượt duyệt lại đọc những cạnh có hai đầu đã được xử lý từ lâu. Thay vào đó, hãy liệt kê các nút mà mỗi nút nối tới, thêm mỗi cạnh vào cả hai danh sách vì bạn có thể đi qua cạnh theo cả hai chiều. Sau đó, dùng hàng đợi để khám phá từ source, thêm vào hàng đợi từng nút kề mà bạn chưa thăm.

Đánh dấu một nút là đã thăm khi bạn thêm nó vào hàng đợi. Như vậy, không nút nào vào hàng đợi hai lần, và quá trình tìm kiếm sẽ kết thúc ngay cả khi có chu trình như 0 → 1 → 2 → 0. Nếu hàng đợi trống trước khi destination được lấy ra, bạn đã thăm mọi nút mà source có thể đến được. Mỗi nút được thêm vào hàng đợi một lần và mỗi cạnh được kiểm tra từ cả hai đầu: thời gian và không gian là O(n + m) với m cạnh.

Thuật toán

Xây dựng danh sách kề: với mỗi cạnh [u, v], thêm v vào danh sách của u và u vào danh sách của v.
Đánh dấu source là đã thăm và đưa nó vào hàng đợi.
Lấy một nút ở đầu hàng đợi. Nếu đó là destination, trả về true.
Đánh dấu và thêm vào hàng đợi từng nút láng giềng chưa được thăm.
Khi hàng đợi trống, trả về false.

from collections import deque


def validPath(n, edges, source, destination):
    # Each edge goes both ways, so list it under both of its ends.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    seen[source] = True
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for nxt in graph[node]:
            if not seen[nxt]:
                # Mark on push, so no node enters the queue twice.
                seen[nxt] = True
                queue.append(nxt)
    return False

Hợp nhất và tìm kiếm

Ý tưởng

Bạn cần biết một đường đi có tồn tại hay không, chứ không cần biết nó là đường đi nào. Bắt đầu bằng cách đặt mỗi nút vào một nhóm riêng. Cạnh [u, v] cho biết u và v thuộc cùng một nhóm, vì vậy hãy gộp các nhóm của chúng. Sau khi xét tất cả các cạnh, source và destination được nối với nhau khi và chỉ khi chúng thuộc cùng một nhóm.

Lưu mỗi nhóm dưới dạng cây gồm các liên kết parent; nút gốc đại diện cho nhóm, còn find(x) lần theo các liên kết lên nút đó. Trong ví dụ thứ hai, [0, 1] và [0, 2] tạo thành {0, 1, 2}, còn [3, 4] tạo thành {3, 4}, nên find(2) và find(4) trả về các nút gốc khác nhau.

Đặt cây nhỏ hơn bên dưới cây lớn hơn, đồng thời cho mỗi nút trỏ đến nút ông của nó trong quá trình find, giúp cây luôn phẳng. Khi đó, mỗi thao tác có chi phí α(n), hàm Ackermann ngược, luôn nhỏ hơn 5 với mọi đầu vào thực tế. Chỉ lưu parent và size: dùng bộ nhớ O(n).

Thuật toán

Đặt parent[x] = x và size[x] = 1 cho mọi nút.
Với mỗi cạnh [u, v], tìm các gốc a và b của hai đầu cạnh.
Nếu chúng khác nhau, đặt gốc của nhóm nhỏ hơn bên dưới gốc còn lại và cộng kích thước của hai nhóm.
Trả về kết quả cho biết find(source) có bằng find(destination) hay không.

def validPath(n, edges, source, destination):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the group's root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        if a != b:
            # Hang the smaller group under the larger one.
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
    return find(source) == find(destination)

Lỗi thường gặp và trường hợp biên

Chỉ thêm mỗi cạnh theo một hướng. Với edges = [[1, 0]], danh sách một chiều không tìm thấy đường đi từ 0 đến 1.
Đánh dấu một nút là đã thấy khi lấy nó ra khỏi hàng đợi. Khi đó, nút sẽ vào hàng đợi một lần cho mỗi nút láng giềng được xử lý trước nó, tối đa 2m lần thay vì n.
Bỏ sót trường hợp source có thể bằng destination. Đáp án là true ngay cả khi nút đó không có cạnh nào.
Dùng DFS đệ quy trên một đường đi dài. Đường đi qua 5000 nút tạo ra 5000 lời gọi lồng nhau, vượt quá giới hạn mặc định là 1000 của Python. Hãy dùng hàng đợi hoặc ngăn xếp tường minh.
So sánh parent[source] với parent[destination] trong cấu trúc union-find. Chỉ các nút gốc mới đại diện cho một nhóm, vì vậy hãy so sánh find(source) với find(destination).

Câu hỏi thường gặp3

Tôi nên dùng BFS, DFS hay union-find để kiểm tra xem có đường đi hay không?

Cả ba đều có độ phức tạp tuyến tính hoặc gần tuyến tính. BFS và DFS có thể dừng ngay khi gặp đích, đồng thời trả về chính đường đi. Union-find không cần danh sách kề và phù hợp với nhiều câu hỏi về tính liên thông trên cùng một đồ thị: sau các lần gộp, mỗi câu hỏi cần hai lần gọi find.

Độ phức tạp thời gian để tìm xem có đường đi trong đồ thị hay không là bao nhiêu?

BFS hoặc DFS cần thời gian và bộ nhớ O(n + m) với n nút và m cạnh. Cấu trúc union-find dùng phép hợp theo kích thước và rút ngắn đường đi cần thời gian O(n + m·α(n)) và bộ nhớ O(n), còn α(n) là một hằng số nhỏ trong thực tế.

Path compression và union by size có tác dụng gì trong union-find?

Chúng giữ cho cây có độ sâu thấp để find luôn chạy nhanh. Phép hợp nhất theo kích thước đặt cây nhỏ hơn bên dưới cây lớn hơn, vì vậy một nút chỉ sâu thêm khi nhóm của nó tăng ít nhất gấp đôi, nhờ đó độ sâu được giới hạn ở mức log n. Nén đường đi hoặc rút ngắn đường đi giúp đường đi đến gốc ngắn hơn mỗi khi chạy find.

def validPath(n, edges, source, destination):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

n = 6
edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
source = 0
destination = 3

Đầu ra mong đợi

true

Find if Path Exists in Graph

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Quét các cạnh cho đến khi không còn gì thay đổi

Tìm kiếm theo chiều rộng

Hợp nhất và tìm kiếm

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự