Find if Path Exists in Graph

Q: Qual é a complexidade de tempo para verificar se existe um caminho em um grafo?

Com BFS ou DFS, o custo é de O(n + m) em tempo e espaço, para n nós e m arestas: cada nó é visitado uma vez e cada aresta é verificada pelas duas extremidades. Union-find com união por tamanho e redução pela metade do caminho custa O(n + m·α(n)) em tempo e O(n) em espaço, em que α cresce tão lentamente que, na prática, é uma constante pequena.

Q: Por que o BFS precisa de um array de visitados?

Sem isso, um ciclo como 0 → 1 → 2 → 0 faz a busca ficar em loop para sempre e, mesmo sem ciclos, um nó com vários vizinhos seria enfileirado uma vez por vizinho. Marcar cada nó no momento em que ele é enfileirado garante que ele seja processado uma única vez, o que limita o trabalho a O(n + m) .

Q: O que a compressão de caminho e a união por tamanho fazem na estrutura union-find?

Elas mantêm as árvores rasas para que find continue rápido. A união por tamanho coloca a árvore menor sob a maior, então a profundidade de um nó só aumenta quando seu grupo pelo menos dobra de tamanho, o que limita a profundidade a log n . A compressão de caminho, ou o encurtamento de caminho usado aqui, reduz o trajeto até a raiz toda vez que você o percorre. Juntas, elas reduzem cada operação a α(n) .

FácilGrafos Union-find

+10

Um grafo não direcionado tem n nós, numerados de 0 a n-1. Cada entrada [u, v] de edges conecta os nós u e v, e você pode percorrer uma aresta em qualquer direção. Retorne true se for possível ir de source a destination pelas arestas, e false caso contrário. Um nó sempre pode alcançar a si mesmo.

Função

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

ninteger: o número de nós
edgesinteger-2d-array: as arestas, cada uma um par [u, v] de nós conectados
sourceinteger: o nó do qual você começa
destinationinteger: o nó que você deseja alcançar
Retornaboolean: se algum caminho une a origem e o destino

Restrições

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] com 0 ≤ u, v ≤ n-1 e u ≠ v
nenhuma aresta aparece duas vezes, em nenhuma das direções.
0 ≤ source, destination ≤ n-1

Exemplos

Entrada: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Saída: true
Explicação: O percurso 0 → 1 → 2 → 3 usa três arestas, então o nó 3 é alcançável. Os nós 4 e 5 formam uma parte separada de que o percurso nunca precisa.

Entrada: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Saída: false
Explicação: A partir do nó 2, você alcança 0 e depois 1, e nada mais. O nó 4 só se conecta ao nó 3, e nenhuma aresta conecta {0, 1, 2} a {3, 4}, então a resposta é false.

+16 testes ocultos ao enviar

Para ir além

Suponha que as arestas sejam de mão única: [u, v] permite que você vá de u para v apenas. Quais das três abordagens ainda funcionam e o que você mudaria nelas?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A questão é se source e destination estão na mesma componente conexa do grafo. A abordagem lenta percorre novamente a lista de arestas até que nenhum novo vértice seja alcançado. Uma busca em largura por uma lista de adjacência explora cada vértice e cada aresta uma vez, e a estrutura union-find obtém a mesma resposta unindo grupos à medida que lê as arestas, sem precisar de listas de vizinhos.

Varra as bordas até que nada mude

Correta, mas não termina nos maiores testes

Intuição

Mantenha uma marca em cada nó que você sabe que pode alcançar, começando por source. Agora leia a lista de arestas. Uma aresta com uma extremidade marcada e outra não marcada significa que você também pode alcançar a extremidade não marcada, então marque-a. Repita a passagem completa até que uma passagem não marque nada de novo ou até que destination esteja marcado.

Isso está correto: um nó em um caminho de comprimento k a partir de source é marcado até a k-ésima passagem, e um nó só é marcado quando uma aresta leva até ele a partir de um nó marcado. No primeiro exemplo, uma passagem na ordem da lista marca 1, 2 e 3 em sequência, e pronto.

O custo depende da ordem das arestas. Se o caminho estiver listado do extremo mais distante para trás, cada passagem marca apenas mais um nó. Um caminho por 5001 nós leva então 5000 passagens por 5000 arestas, 2.5 × 10^7 verificações de arestas, enquanto uma única passagem por uma lista de vizinhos seria suficiente.

Algoritmo

Crie reached com apenas source marcado.
Percorra cada aresta [u, v]. Se exatamente uma extremidade estiver marcada, marque a outra e registre que algo mudou.
Repita a passagem enquanto algo mudar e destination ainda não estiver marcado.
Retorne se 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]

Busca em largura

Intuição

A varredura perde tempo relendo arestas cujas extremidades já foram resolvidas há muito tempo. Em vez disso, liste, para cada nó, os nós aos quais ele está conectado. Cada aresta [u, v] entra nas duas listas, porque você pode percorrê-la nos dois sentidos. Em seguida, explore a partir de source: retire um nó de uma fila e adicione cada vizinho que você ainda não viu.

Marque um nó como visto quando o adicionar à fila, não quando o retirar. Assim, nenhum nó entra na fila duas vezes, e a busca termina mesmo quando o grafo tem ciclos, como 0 → 1 → 2 → 0. Se destination sair da fila em algum momento, existe um caminho. Se a fila ficar vazia antes, você terá visto todos os nós que source pode alcançar, e destination não estará entre eles.

Cada nó é colocado na fila no máximo uma vez e cada aresta é examinada duas vezes, uma a partir de cada extremidade, então o tempo é O(n + m) para m arestas. As listas de vizinhos ocupam O(n + m) de espaço. Uma fila, em vez de recursão, evita que um caminho com 5000 nós cause o estouro da pilha de chamadas.

Algoritmo

Crie uma lista de adjacência: para cada aresta [u, v], adicione v à lista de u e u à lista de v.
Marque source como visitado e coloque-o em uma fila.
Retire um nó do início da fila. Se ele for destination, retorne true.
Marque e coloque na fila cada vizinho que ainda não foi visitado.
Quando a fila estiver vazia, retorne 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ão-busca

Intuição

Você não precisa do caminho, apenas saber se existe um. Portanto, trate o grafo como grupos de nós conectados. No início, cada nó é um grupo por si só. Uma aresta [u, v] indica que u e v pertencem ao mesmo grupo, então una os grupos. Depois de considerar todas as arestas, source e destination estão conectados exatamente quando pertencem ao mesmo grupo.

Armazene cada grupo como uma árvore com ligações parent; a raiz identifica o grupo. find(x) percorre a árvore até a raiz. Para unir, coloque uma raiz sob a outra. No segundo exemplo, [0, 1] e [0, 2] formam o grupo {0, 1, 2}, e [3, 4] forma o grupo {3, 4}; find(2) e find(4) retornam raízes diferentes, então a resposta é false.

Dois hábitos mantêm as árvores achatadas. Coloque o grupo menor sob o maior e reduza pela metade o caminho durante find, apontando cada nó para seu avô. Juntos, eles fazem com que cada operação custe α(n), a função inversa de Ackermann, que permanece abaixo de 5 para qualquer entrada que você venha a encontrar. As arestas são lidas uma única vez, e apenas parent e size são armazenados: espaço O(n) e nenhuma lista de vizinhos para montar.

Algoritmo

Defina parent[x] = x e size[x] = 1 para cada nó.
Para cada aresta [u, v], encontre as raízes a e b de ambas as extremidades.
Se forem diferentes, coloque a raiz do grupo menor abaixo da outra e some os tamanhos.
Retorne se find(source) é 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)

Armadilhas e casos extremos

O grafo é pequeno, mas alguns detalhes determinam se a busca termina e se responde corretamente.

Adicionar cada aresta em apenas uma direção. O grafo é não direcionado, então [1, 0] também deve permitir que você vá de 0 para 1. Uma lista de adjacência unidirecional deixa de incluir caminhos que usam uma aresta no sentido inverso.
Marcar os nós como visitados ao tirá-los da fila, em vez de ao colocá-los nela. Assim, um nó entra na fila uma vez para cada vizinho processado antes dele, então a fila pode conter até 2m entradas, em vez de no máximo n.
Esquecer que source pode ser igual a destination. A resposta é true mesmo quando esse nó não tem nenhuma aresta.
Usar DFS recursiva em um caminho longo. Um caminho que passa por 5000 nós tem 5000 chamadas aninhadas, ultrapassando o limite padrão de 1000 do Python. Use uma fila ou uma pilha explícita.
Comparar parent[source] com parent[destination] na estrutura union-find. Apenas as raízes identificam um grupo; sempre compare find(source) com find(destination).
Esquecer o deslocamento em Lua e R, cujos arrays começam em 1: o nó x fica no índice x+1.

Perguntas frequentes4

Devo usar BFS, DFS ou union-find para verificar se existe um caminho?

Os três são lineares ou quase isso. BFS e DFS podem parar assim que encontram o destino e podem retornar o próprio caminho. A estrutura union-find não precisa de uma lista de adjacência, lê cada aresta uma vez e se destaca quando há muitas perguntas sobre conectividade para o mesmo grafo, porque, após as uniões, cada pergunta custa duas chamadas a find.

Qual é a complexidade de tempo para verificar se existe um caminho em um grafo?

Com BFS ou DFS, o custo é de O(n + m) em tempo e espaço, para n nós e m arestas: cada nó é visitado uma vez e cada aresta é verificada pelas duas extremidades. Union-find com união por tamanho e redução pela metade do caminho custa O(n + m·α(n)) em tempo e O(n) em espaço, em que α cresce tão lentamente que, na prática, é uma constante pequena.

Por que o BFS precisa de um array de visitados?

Sem isso, um ciclo como 0 → 1 → 2 → 0 faz a busca ficar em loop para sempre e, mesmo sem ciclos, um nó com vários vizinhos seria enfileirado uma vez por vizinho. Marcar cada nó no momento em que ele é enfileirado garante que ele seja processado uma única vez, o que limita o trabalho a O(n + m).

O que a compressão de caminho e a união por tamanho fazem na estrutura union-find?

Elas mantêm as árvores rasas para que find continue rápido. A união por tamanho coloca a árvore menor sob a maior, então a profundidade de um nó só aumenta quando seu grupo pelo menos dobra de tamanho, o que limita a profundidade a log n. A compressão de caminho, ou o encurtamento de caminho usado aqui, reduz o trajeto até a raiz toda vez que você o percorre. Juntas, elas reduzem cada operação a α(n).

Python

def validPath(n, edges, source, destination):
    # Escreva o código aqui

Casos de teste

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

Função

Restrições

Exemplos

Dicas

Solução

Varra as bordas até que nada mude

Busca em largura

União-busca

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos