Find if Path Exists in Graph

Q: Qual è la complessità temporale per determinare se esiste un percorso in un grafo?

Con BFS o DFS il tempo e lo spazio sono O(n + m) , per n nodi e m archi: ogni nodo viene visitato una volta e ogni arco viene controllato da entrambe le estremità. Union-find con unione per dimensione e dimezzamento dei percorsi richiede un tempo pari a O(n + m·α(n)) e uno spazio pari a O(n) , dove α cresce così lentamente da essere una piccola costante nella pratica.

Q: Perché BFS ha bisogno di un array dei nodi visitati?

Senza di esso, un ciclo come 0 → 1 → 2 → 0 fa sì che la ricerca continui all'infinito; inoltre, anche in assenza di cicli, un nodo con diversi vicini verrebbe accodato una volta per ogni vicino. Contrassegnare ciascun nodo nel momento in cui viene accodato garantisce che venga elaborato una sola volta, ed è questo che limita il lavoro a O(n + m) .

Q: Che cosa fanno la compressione del percorso e l’unione per dimensione nella struttura union-find?

Mantengono gli alberi poco profondi, così find resta veloce. L’unione per dimensione collega l’albero più piccolo sotto quello più grande, quindi la profondità di un nodo aumenta solo quando il suo gruppo almeno raddoppia, il che limita la profondità a log n . La compressione dei cammini, o il dimezzamento dei cammini usato qui, accorcia il percorso fino alla radice ogni volta che lo percorri. Insieme riducono ogni operazione a α(n) .

FacileGrafi Union-find

+10

Un grafo non orientato ha n nodi, numerati da 0 a n-1. Ogni voce [u, v] di edges collega i nodi u e v e puoi percorrere un arco in entrambe le direzioni. Restituisci true se puoi andare da source a destination lungo gli archi, e false altrimenti. Un nodo può sempre raggiungere sé stesso.

Funzione

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

ninteger: il numero di nodi
edgesinteger-2d-array: gli archi, ciascuno una coppia [u, v] di nodi connessi
sourceinteger: il nodo da cui parti
destinationinteger: il nodo che vuoi raggiungere
Restituisceboolean: se un determinato percorso unisce la sorgente e la destinazione

Vincoli

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] con 0 ≤ u, v ≤ n-1 e u ≠ v
Nessun arco compare due volte, in nessuna delle due direzioni.
0 ≤ source, destination ≤ n-1

Esempi

Input: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Output: true
Spiegazione: Il percorso 0 → 1 → 2 → 3 usa tre archi, quindi il nodo 3 è raggiungibile. I nodi 4 e 5 formano una parte separata di cui il percorso non ha mai bisogno.

Input: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Output: false
Spiegazione: Dal nodo 2 raggiungi 0 e poi 1, e nient’altro. Il nodo 4 tocca solo il nodo 3 e nessun arco collega {0, 1, 2} a {3, 4}, quindi la risposta è false.

+16 test nascosti all’invio

Per approfondire

Supponiamo che gli archi siano a senso unico: [u, v] ti permette di andare da u a v soltanto. Quali dei tre approcci funzionano ancora e cosa modifichi in essi?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La domanda è se source e destination si trovano nella stessa componente connessa del grafo. Il metodo lento esamina di nuovo la lista degli archi finché non viene raggiunto nulla di nuovo. Una ricerca in ampiezza su una lista di adiacenza esplora ogni nodo e ogni arco una sola volta, mentre union-find fornisce la stessa risposta unendo i gruppi man mano che legge gli archi, senza bisogno di liste dei vicini.

Spazza i bordi finché non cambia più nulla

Corretto, ma non termina sui test più grandi

Intuizione

Contrassegna ogni nodo che sai di poter raggiungere, iniziando da source. Ora leggi l’elenco degli archi. Un arco con un’estremità contrassegnata e una non contrassegnata significa che puoi raggiungere anche l’estremità non contrassegnata, quindi contrassegnala. Ripeti l’intera scansione finché una scansione non contrassegna nulla di nuovo oppure destination è contrassegnato.

Questo è corretto: un nodo che si trova a distanza k da source lungo un percorso viene contrassegnato al più tardi durante la k-esima scansione, e un nodo viene contrassegnato solo quando un arco lo raggiunge partendo da un nodo contrassegnato. Nel primo esempio, una scansione nell’ordine dell’elenco contrassegna 1, 2 e 3, in sequenza, e hai finito.

Il costo dipende dall’ordine degli archi. Se il percorso è elencato partendo dall’estremità più lontana e procedendo all’indietro, ogni scansione contrassegna solo un altro nodo. Un percorso attraverso 5001 nodi richiede quindi 5000 scansioni di 5000 archi, cioè 2.5 × 10^7 controlli degli archi, mentre basterebbe una sola scansione dell’elenco dei vicini.

Algoritmo

Crea reached con solo source contrassegnato.
Esamina ogni arco [u, v]. Se esattamente un estremo è contrassegnato, contrassegna l’altro e registra che qualcosa è cambiato.
Ripeti il passaggio finché qualcosa cambia e destination è ancora contrassegnato.
Restituisci se destination è contrassegnato.

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]

Ricerca in ampiezza

Intuizione

La scansione spreca tempo rileggendo archi i cui estremi sono stati sistemati da tempo. Invece, elenca per ogni nodo i nodi che tocca. Ogni arco [u, v] va in entrambe le liste, perché lo puoi percorrere in entrambe le direzioni. Poi esplora verso l’esterno a partire da source: prendi un nodo dalla coda e inserisci ogni vicino che non hai ancora visitato.

Segna un nodo come visitato quando lo inserisci nella coda, non quando lo estrai. In questo modo nessun nodo entra due volte nella coda e la ricerca termina anche quando il grafo contiene cicli, come 0 → 1 → 2 → 0. Se destination viene estratto dalla coda, esiste un percorso. Se la coda si svuota prima, hai visitato tutti i nodi raggiungibili da source, e destination non era tra questi.

Ogni nodo viene inserito in coda al massimo una volta e ogni arco viene esaminato due volte, una da ciascun estremo, quindi il tempo è O(n + m) per m archi. Le liste dei vicini occupano O(n + m) spazio. Usare una coda invece della ricorsione evita che un percorso di 5000 nodi faccia traboccare lo stack delle chiamate.

Algoritmo

Crea una lista di adiacenza: per ogni arco [u, v], aggiungi v alla lista di u e u alla lista di v.
Segna source come visitato e inseriscilo in una coda.
Prendi un nodo dalla testa della coda. Se è destination, restituisci true.
Segna e aggiungi alla coda ogni vicino non ancora visitato.
Quando la coda è vuota, restituisci 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

Intuizione

Non ti serve il percorso, solo sapere se ne esiste uno. Quindi considera il grafo come gruppi di nodi connessi. All’inizio ogni nodo forma un gruppo a sé. Un arco [u, v] indica che u e v appartengono allo stesso gruppo, quindi unisci i loro gruppi. Dopo aver considerato tutti gli archi, source e destination sono connessi esattamente quando appartengono allo stesso gruppo.

Memorizza ogni gruppo come un albero con collegamenti parent; la radice identifica il gruppo. find(x) risale fino alla radice. Per unire due gruppi, collega una radice all’altra. Nel secondo esempio, [0, 1] e [0, 2] formano il gruppo {0, 1, 2} e [3, 4] forma {3, 4}; find(2) e find(4) restituiscono radici diverse, quindi la risposta è false.

Due accorgimenti mantengono gli alberi piatti. Collega il gruppo più piccolo sotto quello più grande e dimezza il percorso durante find, puntando ogni nodo al proprio nonno. Insieme fanno sì che ogni operazione abbia un costo di α(n), la funzione inversa di Ackermann, che resta inferiore a 5 per qualsiasi input che potrai mai incontrare. Gli archi vengono letti una sola volta e si memorizzano solo parent e size: spazio O(n) e nessun elenco di vicini da costruire.

Algoritmo

Imposta parent[x] = x e size[x] = 1 per ogni nodo.
Per ogni arco [u, v], trova le radici a e b di entrambe le estremità.
Se sono diverse, collega la radice del gruppo più piccolo sotto l’altra e somma le dimensioni.
Restituisci se find(source) è uguale a 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)

Trappole e casi limite

Il grafo è piccolo, ma alcuni dettagli determinano se la ricerca termina e restituisce la risposta corretta.

Aggiungere ogni arco in una sola direzione. Il grafo non è orientato, quindi [1, 0] deve permetterti di andare anche da 0 a 1. Una lista di adiacenza a senso unico non rileva i percorsi che usano un arco al contrario.
Contrassegnare i nodi come visitati quando li estrai dalla coda invece che quando li inserisci. Un nodo entra quindi nella coda una volta per ogni vicino elaborato prima di lui, perciò la coda può contenere fino a 2m elementi invece che al massimo n.
Dimenticare che source può essere uguale a destination. La risposta è true anche quando quel nodo non ha alcun arco.
Usare una DFS ricorsiva su un percorso lungo. Un percorso attraverso 5000 nodi comporta 5000 chiamate annidate, superando il limite predefinito di 1000 di Python. Usa una coda o uno stack esplicito.
Confrontare parent[source] con parent[destination] nella struttura union-find. Solo le radici identificano un gruppo; confronta sempre find(source) con find(destination).
Dimenticare lo spostamento di indice in Lua e R, i cui array iniziano da 1: il nodo x si trova all'indice x+1.

Domande frequenti4

Dovrei usare BFS, DFS o union-find per verificare se esiste un percorso?

Tutti e tre sono lineari o quasi. BFS e DFS possono fermarsi non appena raggiungono la destinazione e possono restituire il percorso stesso. Union-find non ha bisogno di una lista di adiacenza, legge ogni arco una sola volta ed è particolarmente efficace quando si pongono molte domande sulla connettività dello stesso grafo, perché dopo le unioni ogni domanda richiede due chiamate a find.

Qual è la complessità temporale per determinare se esiste un percorso in un grafo?

Con BFS o DFS il tempo e lo spazio sono O(n + m), per n nodi e m archi: ogni nodo viene visitato una volta e ogni arco viene controllato da entrambe le estremità. Union-find con unione per dimensione e dimezzamento dei percorsi richiede un tempo pari a O(n + m·α(n)) e uno spazio pari a O(n), dove α cresce così lentamente da essere una piccola costante nella pratica.

Perché BFS ha bisogno di un array dei nodi visitati?

Senza di esso, un ciclo come 0 → 1 → 2 → 0 fa sì che la ricerca continui all'infinito; inoltre, anche in assenza di cicli, un nodo con diversi vicini verrebbe accodato una volta per ogni vicino. Contrassegnare ciascun nodo nel momento in cui viene accodato garantisce che venga elaborato una sola volta, ed è questo che limita il lavoro a O(n + m).

Che cosa fanno la compressione del percorso e l’unione per dimensione nella struttura union-find?

Mantengono gli alberi poco profondi, così find resta veloce. L’unione per dimensione collega l’albero più piccolo sotto quello più grande, quindi la profondità di un nodo aumenta solo quando il suo gruppo almeno raddoppia, il che limita la profondità a log n. La compressione dei cammini, o il dimezzamento dei cammini usato qui, accorcia il percorso fino alla radice ogni volta che lo percorri. Insieme riducono ogni operazione a α(n).

Python

def validPath(n, edges, source, destination):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso

true

Find if Path Exists in Graph

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Spazza i bordi finché non cambia più nulla

Ricerca in ampiezza

Union-find

Trappole e casi limite

Domande frequenti4

Problemi simili