Find if Path Exists in Graph

Q: ¿Cuál es la complejidad temporal de determinar si existe un camino en un grafo?

Con BFS o DFS, el tiempo y el espacio son O(n + m) , para n nodos y m aristas: cada nodo se visita una vez y cada arista se comprueba desde ambos extremos. Union-find con unión por tamaño y compresión de caminos a la mitad cuesta O(n + m·α(n)) de tiempo y O(n) de espacio, donde α crece tan lentamente que, en la práctica, es una constante pequeña.

Q: ¿Por qué BFS necesita un arreglo de visitados?

Sin ello, un ciclo como 0 → 1 → 2 → 0 hace que la búsqueda dé vueltas sin parar, y aun sin ciclos, un nodo con varios vecinos se pondría en la cola una vez por cada vecino. Marcar cada nodo en el momento en que se pone en la cola garantiza que se procese una sola vez, lo que limita el trabajo a O(n + m) .

Q: ¿Qué hacen la compresión de caminos y la unión por tamaño en union-find?

Mantienen los árboles poco profundos para que find siga siendo rápido. La unión por tamaño cuelga el árbol más pequeño debajo del más grande, por lo que la profundidad de un nodo solo aumenta cuando su grupo al menos se duplica, lo que limita la profundidad a log n . La compresión de caminos, o la división de caminos que se usa aquí, acorta el recorrido hasta la raíz cada vez que lo haces. Juntos, reducen cada operación a α(n) .

FácilGrafos Union-find

+10

Un grafo no dirigido tiene n nodos, numerados del 0 al n-1. Cada entrada [u, v] de edges conecta los nodos u y v, y puedes recorrer una arista en cualquiera de las dos direcciones. Devuelve true si puedes ir de source a destination a lo largo de las aristas, y false en caso contrario. Un nodo siempre puede llegar a sí mismo.

Función

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

ninteger: el número de nodos
edgesinteger-2d-array: las aristas, cada una un par [u, v] de nodos conectados
sourceinteger: el nodo desde el que empiezas
destinationinteger: el nodo al que quieres llegar
Devuelveboolean: si alguna ruta une el origen y el destino

Restricciones

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] con 0 ≤ u, v ≤ n-1 y u ≠ v
No hay ninguna arista que aparezca dos veces, en ninguna dirección.
0 ≤ source, destination ≤ n-1

Ejemplos

Entrada: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Salida: true
Explicación: El recorrido 0 → 1 → 2 → 3 usa tres aristas, así que el nodo 3 es alcanzable. Los nodos 4 y 5 forman una parte separada que el recorrido nunca necesita.

Entrada: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Salida: false
Explicación: Desde el nodo 2 llegas a 0 y después a 1, y a nada más. El nodo 4 solo toca el nodo 3, y ninguna arista conecta {0, 1, 2} con {3, 4}, así que la respuesta es false.

+16 pruebas ocultas al enviar

Para ir más allá

Supón que las aristas son unidireccionales: [u, v] te permite ir de u a v solamente. ¿Cuáles de los tres enfoques siguen funcionando y qué cambias en ellos?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La pregunta es si source y destination se encuentran en la misma componente conexa del grafo. El método lento vuelve a recorrer la lista de aristas hasta que ya no se alcanza nada nuevo. Una búsqueda en anchura sobre una lista de adyacencia explora cada nodo y cada arista una vez, y union-find obtiene la misma respuesta fusionando grupos mientras lee las aristas, sin necesidad de listas de vecinos.

Recorre los bordes hasta que nada cambie

Correcto, pero no termina con las pruebas más grandes

Intuición

Marca cada nodo que sepas que puedes alcanzar, empezando por source. Ahora lee la lista de aristas. Una arista con un extremo marcado y otro sin marcar significa que también puedes alcanzar el extremo sin marcar, así que márcalo. Repite todo el recorrido hasta que uno no marque nada nuevo, o hasta que destination esté marcado.

Esto es correcto: un nodo que está a una distancia de k en un camino desde source queda marcado, como máximo, en el k-ésimo recorrido, y un nodo solo se marca cuando una arista llega hasta él desde un nodo marcado. En el primer ejemplo, un recorrido en el orden de la lista marca 1, 2 y 3, en ese orden, y ya has terminado.

El coste depende del orden de las aristas. Si el camino aparece en la lista desde el extremo más lejano hacia atrás, cada recorrido marca solo un nodo más. Un camino que atraviesa 5001 nodos requiere entonces 5000 recorridos de 5000 aristas, es decir, 2.5 × 10^7 comprobaciones de aristas, cuando bastaría con recorrer una lista de vecinos.

Algoritmo

Crea reached con solo source marcado.
Recorre cada arista [u, v]. Si exactamente un extremo está marcado, marca el otro y registra que hubo un cambio.
Repite el recorrido mientras haya habido algún cambio y destination siga sin marcar.
Devuelve si destination está marcado.

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]

Búsqueda en anchura

Intuición

El recorrido pierde tiempo volviendo a leer aristas cuyos extremos ya se establecieron hace mucho. En su lugar, haz una lista de los nodos que toca cada nodo. Cada arista [u, v] va en ambas listas, porque puedes recorrerla en ambos sentidos. Después explora hacia afuera desde source: toma un nodo de una cola y añade cada vecino que aún no hayas visto.

Marca un nodo como visto cuando lo añadas a la cola, no cuando lo saques. Así, ningún nodo entra dos veces en la cola y la búsqueda termina incluso cuando el grafo tiene ciclos, como 0 → 1 → 2 → 0. Si destination sale de la cola, existe un camino. Si la cola se vacía primero, habrás visto todos los nodos a los que puede llegar source, y destination no estaba entre ellos.

Cada nodo se añade a la cola como máximo una vez y cada arista se examina dos veces, una desde cada extremo, así que el tiempo es O(n + m) para m aristas. Las listas de vecinos ocupan O(n + m) espacio. Usar una cola en lugar de la recursión evita que un camino de 5000 nodos desborde la pila de llamadas.

Algoritmo

Construye una lista de adyacencia: para cada arista [u, v], añade v a la lista de u y u a la lista de v.
Marca source como visitado y ponlo en una cola.
Toma un nodo del frente. Si es destination, devuelve true.
Marca y añade a la cola cada vecino que aún no se haya visitado.
Cuando la cola esté vacía, devuelve 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

Unión-búsqueda

Intuición

No necesitas conocer el camino, solo saber si existe uno. Así que trata el grafo como grupos de nodos conectados. Al principio, cada nodo forma su propio grupo. Una arista [u, v] indica que u y v pertenecen al mismo grupo, así que combina sus grupos. Después de procesar todas las aristas, source y destination están conectados exactamente cuando pertenecen al mismo grupo.

Guarda cada grupo como un árbol con enlaces parent; la raíz identifica el grupo. find(x) sube hasta la raíz. Para combinar grupos, cuelga una raíz debajo de la otra. En el segundo ejemplo, [0, 1] y [0, 2] forman el grupo {0, 1, 2} y [3, 4] forma {3, 4}; find(2) y find(4) devuelven raíces distintas, así que la respuesta es false.

Dos hábitos mantienen los árboles planos. Cuelga el grupo más pequeño debajo del más grande y reduce a la mitad el camino durante find haciendo que cada nodo apunte a su abuelo. Juntos hacen que cada operación cueste α(n), la función inversa de Ackermann, que se mantiene por debajo de 5 para cualquier entrada que llegues a ver. Las aristas se leen una sola vez y solo se almacenan parent y size: espacio O(n) y no hay que construir listas de vecinos.

Algoritmo

Establece parent[x] = x y size[x] = 1 para cada nodo.
Para cada arista [u, v], encuentra las raíces a y b de ambos extremos.
Si son diferentes, cuelga la raíz del grupo más pequeño bajo la otra y suma los tamaños.
Devuelve si find(source) es igual 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)

Errores comunes y casos límite

El grafo es pequeño, pero unos cuantos detalles determinan si la búsqueda termina y responde correctamente.

Agregar cada arista en una sola dirección. El grafo no está dirigido, así que [1, 0] debe permitirte recorrer también el camino de 0 a 1. Una lista de adyacencia unidireccional omite los caminos que usan una arista en sentido inverso.
Marcar los nodos como vistos cuando los sacas de la cola en lugar de cuando los pones en ella. Entonces, un nodo entra en la cola una vez por cada vecino procesado antes que él, así que la cola puede contener hasta 2m entradas en lugar de como máximo n.
Olvidar que source puede ser igual a destination. La respuesta es true incluso cuando ese nodo no tiene ninguna arista.
Usar DFS recursivo en un camino largo. Un camino a través de 5000 nodos implica 5000 llamadas anidadas, lo que supera el límite predeterminado de Python de 1000. Usa una cola o una pila explícita.
Comparar parent[source] con parent[destination] en union-find. Solo las raíces identifican un grupo; compara siempre find(source) con find(destination).
Olvidar el desplazamiento en Lua y R, cuyos arreglos empiezan en 1: el nodo x se encuentra en el índice x+1.

Preguntas frecuentes4

¿Debería usar BFS, DFS o union-find para comprobar si existe una ruta?

Los tres son lineales o casi lineales. BFS y DFS pueden detenerse en cuanto llegan al destino, y pueden devolver la ruta en sí. Union-find no necesita una lista de adyacencia, lee cada arista una vez y destaca cuando se plantean muchas preguntas de conectividad sobre el mismo grafo, porque después de las fusiones cada pregunta cuesta dos llamadas a find.

¿Cuál es la complejidad temporal de determinar si existe un camino en un grafo?

Con BFS o DFS, el tiempo y el espacio son O(n + m), para n nodos y m aristas: cada nodo se visita una vez y cada arista se comprueba desde ambos extremos. Union-find con unión por tamaño y compresión de caminos a la mitad cuesta O(n + m·α(n)) de tiempo y O(n) de espacio, donde α crece tan lentamente que, en la práctica, es una constante pequeña.

¿Por qué BFS necesita un arreglo de visitados?

Sin ello, un ciclo como 0 → 1 → 2 → 0 hace que la búsqueda dé vueltas sin parar, y aun sin ciclos, un nodo con varios vecinos se pondría en la cola una vez por cada vecino. Marcar cada nodo en el momento en que se pone en la cola garantiza que se procese una sola vez, lo que limita el trabajo a O(n + m).

¿Qué hacen la compresión de caminos y la unión por tamaño en union-find?

Mantienen los árboles poco profundos para que find siga siendo rápido. La unión por tamaño cuelga el árbol más pequeño debajo del más grande, por lo que la profundidad de un nodo solo aumenta cuando su grupo al menos se duplica, lo que limita la profundidad a log n. La compresión de caminos, o la división de caminos que se usa aquí, acorta el recorrido hasta la raíz cada vez que lo haces. Juntos, reducen cada operación a α(n).

Python

def validPath(n, edges, source, destination):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

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

Esperado

true

Find if Path Exists in Graph

Función

Restricciones

Ejemplos

Pistas

Solución

Recorre los bordes hasta que nada cambie

Búsqueda en anchura

Unión-búsqueda

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares