Find if Path Exists in Graph

Q: Dlaczego BFS potrzebuje tablicy odwiedzonych wierzchołków?

Bez tego cykl taki jak 0 → 1 → 2 → 0 sprawia, że wyszukiwanie krąży bez końca, a nawet bez cykli węzeł z kilkoma sąsiadami zostałby umieszczony w kolejce raz dla każdego sąsiada. Oznaczenie każdego węzła w chwili umieszczenia go w kolejce gwarantuje, że zostanie przetworzony tylko raz, co ogranicza ilość pracy do O(n + m) .

Q: Co robią kompresja ścieżek i łączenie według rozmiaru w strukturze union-find?

Utrzymują drzewa płytkie, dzięki czemu find działa szybko. Łączenie według rozmiaru podwiesza mniejsze drzewo pod większym, więc głębokość węzła rośnie tylko wtedy, gdy jego grupa co najmniej się podwaja, co ogranicza głębokość do log n . Kompresja ścieżki, a konkretnie stosowane tutaj skracanie ścieżki, skraca drogę do korzenia za każdym razem, gdy ją pokonujesz. Razem obie te metody zmniejszają koszt każdej operacji do α(n) .

ŁatweGrafy Union-find

+10

Graf nieskierowany ma n węzłów, ponumerowanych od 0 do n-1. Każdy element [u, v] tablicy edges łączy węzły u i v, a krawędź można przemierzać w obu kierunkach. Zwróć true, jeśli można przejść od source do destination wzdłuż krawędzi, a w przeciwnym razie false. Węzeł zawsze może dotrzeć do samego siebie.

Funkcja

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

ninteger: liczba węzłów
edgesinteger-2d-array: krawędzie, z których każda jest parą [u, v] połączonych węzłów
sourceinteger: węzeł, od którego zaczynasz
destinationinteger: węzeł, do którego chcesz dotrzeć
Zwracaboolean: czy jakaś ścieżka łączy źródło i cel

Ograniczenia

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] przy 0 ≤ u, v ≤ n-1 i u ≠ v
Żadna krawędź nie występuje dwukrotnie, w żadnym kierunku.
0 ≤ source, destination ≤ n-1

Przykłady

Wejście: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Wyjście: true
Wyjaśnienie: Ścieżka 0 → 1 → 2 → 3 wykorzystuje trzy krawędzie, więc węzeł 3 jest osiągalny. Węzły 4 i 5 tworzą osobną część, której nie obejmuje ta ścieżka.

Wejście: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Wyjście: false
Wyjaśnienie: Z węzła 2 docierasz do 0, a następnie do 1, i do żadnego innego węzła. Węzeł 4 łączy się tylko z węzłem 3, a żadna krawędź nie łączy {0, 1, 2} z {3, 4}, więc odpowiedź to false.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że krawędzie są jednokierunkowe: [u, v] pozwala przejść tylko z u do v. Które z trzech podejść nadal działają i co należy w nich zmienić?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Pytanie brzmi, czy source i destination znajdują się w tej samej spójnej części grafu. Powolna metoda ponownie przegląda listę krawędzi, aż nie da się już dotrzeć do żadnego nowego wierzchołka. Wyszukiwanie wszerz na liście sąsiedztwa odwiedza każdy wierzchołek i każdą krawędź raz, a struktura union-find uzyskuje tę samą odpowiedź, łącząc grupy podczas odczytywania krawędzi, bez żadnych list sąsiadów.

Przesuwaj krawędzie, aż nic się nie zmieni

Poprawne, ale nie kończy się na największych testach

Intuicja

Oznacz każdy węzeł, o którym wiesz, że możesz do niego dotrzeć, zaczynając od source. Następnie przejrzyj listę krawędzi. Krawędź z jednym oznaczonym i jednym nieoznaczonym końcem oznacza, że możesz dotrzeć także do nieoznaczonego końca, więc go oznacz. Powtarzaj całe przejście, aż żadne przejście nie oznaczy niczego nowego lub zostanie oznaczony destination.

To jest poprawne: węzeł na ścieżce długości k od source zostanie oznaczony najpóźniej podczas k-tego przejścia, a węzeł jest oznaczany tylko wtedy, gdy prowadzi do niego krawędź z oznaczonego węzła. W pierwszym przykładzie jedno przejście w kolejności z listy oznacza kolejno 1, 2 i 3, i to wystarczy.

Koszt zależy od kolejności krawędzi. Jeśli ścieżka jest wypisana od dalszego końca wstecz, każde przejście oznacza tylko jeden kolejny węzeł. Ścieżka przez 5001 węzłów wymaga wtedy 5000 przejść po 5000 krawędziach, czyli 2.5 × 10^7 sprawdzeń krawędzi, podczas gdy wystarczyłoby jedno przejście po liście sąsiadów.

Algorytm

Utwórz reached, oznaczając tylko source.
Przejdź przez każdą krawędź [u, v]. Jeśli dokładnie jeden koniec jest oznaczony, oznacz drugi i zapisz, że coś się zmieniło.
Powtarzaj przejście, dopóki coś się zmienia, a destination pozostaje nieoznaczone.
Zwróć informację, czy destination jest oznaczone.

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]

Przeszukiwanie wszerz

Intuicja

Przeszukiwanie marnuje czas na ponowne odczytywanie krawędzi, których końce zostały już dawno rozpatrzone. Zamiast tego wypisz dla każdego węzła węzły, z którymi jest połączony. Każda krawędź [u, v] trafia na obie listy, ponieważ można przejść nią w obu kierunkach. Następnie przeszukuj graf, zaczynając od source: pobierz węzeł z kolejki i dodaj do niej każdego sąsiada, którego jeszcze nie odwiedzono.

Oznacz węzeł jako odwiedzony w chwili dodawania go do kolejki, a nie podczas pobierania. Dzięki temu żaden węzeł nie trafi do kolejki dwa razy, a wyszukiwanie zakończy się nawet wtedy, gdy graf zawiera cykle, takie jak 0 → 1 → 2 → 0. Jeśli destination zostanie pobrany z kolejki, istnieje ścieżka. Jeśli kolejka opróżni się wcześniej, oznacza to, że odwiedzono wszystkie węzły osiągalne z source, a destination wśród nich nie było.

Każdy węzeł trafia do kolejki najwyżej raz, a każda krawędź jest sprawdzana dwa razy, po jednym razie z każdego końca, więc czas działania wynosi O(n + m) dla m krawędzi. Listy sąsiadów zajmują O(n + m) pamięci. Użycie kolejki zamiast rekurencji zapobiega przepełnieniu stosu wywołań podczas przeszukiwania ścieżki składającej się z 5000 węzłów.

Algorytm

Zbuduj listę sąsiedztwa: dla każdej krawędzi [u, v] dodaj v do listy u i u do listy v.
Oznacz source jako odwiedzony i umieść go w kolejce.
Weź węzeł z początku kolejki. Jeśli jest to destination, zwróć true.
Oznacz i dodaj do kolejki każdego sąsiada, który nie został jeszcze odwiedzony.
Gdy kolejka będzie pusta, zwróć 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

Union-find

Intuicja

Nie potrzebujesz ścieżki, a jedynie informacji, czy jakaś istnieje. Potraktuj więc graf jako grupy połączonych węzłów. Na początku każdy węzeł tworzy własną grupę. Krawędź [u, v] oznacza, że u i v należą do tej samej grupy, więc połącz ich grupy. Po przetworzeniu wszystkich krawędzi source i destination są połączone wtedy i tylko wtedy, gdy należą do tej samej grupy.

Przechowuj każdą grupę jako drzewo z odnośnikami parent; korzeń wskazuje grupę. find(x) przechodzi w górę aż do korzenia. Aby połączyć grupy, umieść jeden korzeń pod drugim. W drugim przykładzie [0, 1] i [0, 2] tworzą grupę {0, 1, 2}, a [3, 4] tworzy grupę {3, 4}; find(2) i find(4) zwracają różne korzenie, więc odpowiedź to false.

Dwa nawyki utrzymują płaską strukturę drzew. Umieszczaj mniejszą grupę pod większą, a podczas find skracaj ścieżkę o połowę, wskazując z każdego węzła na jego dziadka. Razem sprawiają, że koszt każdej operacji wynosi α(n), czyli odwrotną funkcję Ackermanna, której wartość pozostaje mniejsza niż 5 dla dowolnych danych wejściowych, jakie kiedykolwiek napotkasz. Krawędzie są odczytywane raz, a przechowywane są tylko parent i size: pamięć O(n) i brak konieczności tworzenia list sąsiadów.

Algorytm

Ustaw parent[x] = x i size[x] = 1 dla każdego węzła.
Dla każdej krawędzi [u, v] znajdź korzenie a i b obu końców.
Jeśli są różne, podłącz korzeń mniejszej grupy pod drugi i dodaj rozmiary.
Zwróć informację, czy find(source) jest równe find(destination).

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)

Pułapki i przypadki brzegowe

Graf jest mały, ale kilka szczegółów decyduje o tym, czy wyszukiwanie się zakończy i czy poda prawidłową odpowiedź.

Dodawanie każdej krawędzi tylko w jednym kierunku. Graf jest nieskierowany, więc [1, 0] musi umożliwiać przejście z 0 do 1. Lista sąsiedztwa zawierająca połączenia tylko w jedną stronę pomija ścieżki wykorzystujące krawędź w przeciwnym kierunku.
Oznaczanie węzłów jako odwiedzonych podczas wyjmowania ich z kolejki zamiast podczas dodawania do niej. Węzeł trafia wtedy do kolejki raz dla każdego sąsiada przetworzonego przed nim, więc kolejka może zawierać do 2m elementów zamiast co najwyżej n.
Zapominanie, że source może być równe destination. Odpowiedzią jest true, nawet gdy ten węzeł nie ma żadnych krawędzi.
Używanie rekurencyjnego DFS na długiej ścieżce. Ścieżka przez 5000 węzłów oznacza 5000 zagnieżdżonych wywołań, czyli przekroczenie domyślnego limitu Pythona wynoszącego 1000. Użyj kolejki albo jawnego stosu.
Porównywanie parent[source] z parent[destination] w strukturze union-find. Grupę określają tylko korzenie; zawsze porównuj find(source) z find(destination).
Zapominanie o przesunięciu w Lua i R, gdzie tablice zaczynają się od 1: węzeł x znajduje się pod indeksem x+1.

Najczęstsze pytania4

Czy użyć BFS, DFS czy struktury union-find, aby sprawdzić, czy istnieje ścieżka?

Wszystkie trzy mają złożoność liniową lub zbliżoną do liniowej. BFS i DFS mogą zatrzymać się, gdy tylko dotrą do celu, i mogą zwrócić samą ścieżkę. Union-find nie wymaga listy sąsiedztwa, odczytuje każdą krawędź raz i sprawdza się doskonale, gdy dla tego samego grafu pojawia się wiele pytań o spójność, ponieważ po połączeniach każde pytanie wymaga dwóch wywołań find.

Jaka jest złożoność czasowa sprawdzania, czy w grafie istnieje ścieżka?

W przypadku BFS lub DFS złożoność czasowa i pamięciowa wynosi O(n + m), dla n węzłów i m krawędzi: każdy węzeł jest odwiedzany raz, a każda krawędź jest sprawdzana z obu końców. Struktura union-find z łączeniem według rozmiaru i spłaszczaniem ścieżek ma złożoność czasową O(n + m·α(n)) i pamięciową O(n), gdzie α rośnie tak wolno, że w praktyce jest małą stałą.

Dlaczego BFS potrzebuje tablicy odwiedzonych wierzchołków?

Bez tego cykl taki jak 0 → 1 → 2 → 0 sprawia, że wyszukiwanie krąży bez końca, a nawet bez cykli węzeł z kilkoma sąsiadami zostałby umieszczony w kolejce raz dla każdego sąsiada. Oznaczenie każdego węzła w chwili umieszczenia go w kolejce gwarantuje, że zostanie przetworzony tylko raz, co ogranicza ilość pracy do O(n + m).

Co robią kompresja ścieżek i łączenie według rozmiaru w strukturze union-find?

Utrzymują drzewa płytkie, dzięki czemu find działa szybko. Łączenie według rozmiaru podwiesza mniejsze drzewo pod większym, więc głębokość węzła rośnie tylko wtedy, gdy jego grupa co najmniej się podwaja, co ogranicza głębokość do log n. Kompresja ścieżki, a konkretnie stosowane tutaj skracanie ścieżki, skraca drogę do korzenia za każdym razem, gdy ją pokonujesz. Razem obie te metody zmniejszają koszt każdej operacji do α(n).

Python

def validPath(n, edges, source, destination):
    # Wpisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

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

Oczekiwane

true

Find if Path Exists in Graph

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Przesuwaj krawędzie, aż nic się nie zmieni

Przeszukiwanie wszerz

Union-find

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania