Graph: BFS & DFS

Categoria: Graphs

O problema

Toda estrutura em outro lugar deste repositório responde "encontre o valor para esta chave" — uma hash table, uma BST, uma B-tree, todas indexam entradas individuais. Nenhuma delas responde a um tipo diferente de pergunta: dado como um conjunto de coisas está conectado entre si, quais delas podem ser alcançadas a partir de um ponto de partida, seguindo quantos saltos forem necessários? Uma Hash Table pode dizer se a conta A tem uma aresta direta para a conta B. Ela não pode dizer se a conta A está conectada à conta F através de três contas intermediárias, porque essa é uma pergunta sobre a forma de um grafo de relacionamentos, não sobre uma única chave.

A solução

Modele os relacionamentos como uma lista de adjacência — Map<T, List<T>> — em que a lista de cada chave é tudo o que está diretamente conectado a ela, e percorra-a sistematicamente para que nenhum vértice alcançável seja perdido e nenhum seja visitado duas vezes. Este módulo implementa as duas ordens clássicas de percurso:

• BFS (busca em largura): visita tudo que está a um salto de distância, depois tudo que está a dois saltos, e assim por diante, usando uma fila FIFO. Os vértices são marcados como visitados no momento em que são enfileirados, não quando são desenfileirados — como dois vizinhos diferentes podem apontar para o mesmo vértice ainda não visitado, marcar apenas no momento do desenfileiramento permitiria que ele fosse enfileirado duas vezes e aparecesse duas vezes no resultado.
• DFS (busca em profundidade): vai o mais fundo possível em um caminho antes de retroceder, usando uma pilha. Esta implementação é iterativa, com uma Deque explícita usada como pilha, deliberadamente não recursiva — uma DFS recursiva se lê de forma mais natural, mas cada chamada recursiva consome um frame de pilha nativo da JVM, então um grafo suficientemente grande ou profundo (uma longa cadeia de contas vinculadas, por exemplo) corre o risco de um StackOverflowError, algo que uma pilha explícita alocada no heap simplesmente não pode atingir.

Ambas descobrem exatamente o mesmo conjunto de vértices alcançáveis a partir de um ponto de partida — apenas a ordem difere — e ambas fazem isso em O(V + E): cada vértice é visitado uma vez, e cada aresta é examinada no máximo duas vezes (uma vez a partir de cada extremidade).

flowchart LR
    A((A)) --- B((B))
    A --- C((C))
    B --- D((D))
    C --- D
    E((E)) --- F((F))

Iniciando um percurso a partir de A acima: BFS visita A, B, C, D (um salto, depois dois); DFS visita A, B, D, C (até o fim de um caminho, depois retrocede). Nenhuma das duas jamais alcança E ou F — eles são um componente conectado separado, inalcançável a partir de A não importa qual percurso seja usado.

Exemplo clássico

classic/Graph é um grafo não direcionado e não ponderado, construído sobre uma lista de adjacência Map<T, List<T>> feita à mão — addEdge liga as duas direções, e bfs/dfs retornam a ordem de visita como uma List<T>. GraphTest constrói um grafo com um ciclo (de modo que ambos os percursos sejam forçados a descartar um vizinho já visitado pelo menos uma vez) mais um componente desconectado (de modo que ambos os percursos sejam verificados para nunca entrar nele), e cobre o caso de falha de vértice inicial desconhecido tanto para bfs quanto para dfs.

Exemplo aplicado: percurso de rede AML

applied/AmlNetworkTraversal modela relações de transação entre contas como um grafo para uma investigação de compliance de prevenção à lavagem de dinheiro: dada uma conta sinalizada, o BFS a partir dela encontra toda outra conta alcançável através de quantos saltos de transação forem necessários — o cluster conectado completo potencialmente envolvido no mesmo esquema, não apenas as contrapartes diretas da conta sinalizada, o que uma consulta mais simples do tipo "com quem esta conta transacionou" deixaria passar por completo. AmlNetworkTraversalTest cobre um cluster de múltiplos saltos, confirma que contas mais próximas aparecem antes das mais distantes, e confirma que contas fora da rede sinalizada nunca aparecem no resultado.

Benchmark

./gradlew :graphs:graph-bfs-dfs:jmh

Execução real (JMH 1.37, JDK 26.0.2, 2 iterações de aquecimento + 3 iterações de medição, 1 fork). A contagem de vértices e arestas cresce junto em uma densidade fixa (4 arestas adicionadas por vértice, com semente Random(42)), então, se a afirmação de O(V + E) for válida, o tempo total de percurso deve crescer aproximadamente na mesma proporção que a contagem de vértices. O @Setup de cada execução confirmou que o grafo inteiro permaneceu como um único componente conectado em todos os tamanhos (tanto BFS quanto DFS visitaram todos os V vértices a partir do vértice inicial, nos três tamanhos):

Normalizado por vértice, isso é aproximadamente 240-340 ns/vértice em size=1,000, 580-895 ns/vértice em size=10,000, e 1,480-1,750 ns/vértice em size=100,000 — crescendo, mas longe do crescimento de ~10x por década que um percurso O(V^2) mostraria com densidade de arestas constante; está bem aquém até de uma ordem de grandeza de crescimento no custo por vértice ao longo de duas ordens de grandeza na contagem de vértices, o que é consistente com O(V + E). O número por vértice não é perfeitamente estável como o de um benchmark verdadeiramente O(1) em outro lugar deste repositório, e os intervalos de confiança em size=10,000 e 100,000 são largos (o ruído de JVM/GC na casa de milissegundos de um único dígito domina nessa contagem de iterações) — ambos os percursos alocam um novo conjunto de visitados e uma nova lista de resultado a cada única invocação aqui, então parte desse crescimento é, realisticamente, pressão de GC/alocação que escala com a pegada de heap, não o próprio algoritmo de grafo se tornando menos linear.

Quando não usar

• Precisa do caminho mais curto ponderado, não apenas de alcançabilidade ou do menor número de saltos? O BFS simples só encontra caminhos mais curtos quando toda aresta tem o mesmo peso (como aqui); um grafo ponderado precisa do algoritmo de Dijkstra ou similar.
• Precisa saber apenas os poucos vértices alcançáveis mais próximos, não o conjunto alcançável inteiro? Ambos os percursos aqui sempre rodam até o fim — uma variante com saída antecipada (parar assim que um alvo for encontrado, ou assim que um limite de distância em saltos for excedido) desperdiçaria menos trabalho para essa pergunta mais restrita.
• Este grafo é apenas não direcionado — addEdge sempre liga as duas direções. Relacionamentos que são inerentemente de mão única (dinheiro fluindo de A para B não implica o inverso) precisam de um grafo direcionado, o que este módulo não modela.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :graphs:graph-bfs-dfs:jacocoTestReport

Relatório em graphs/graph-bfs-dfs/build/reports/jacoco/test/html/index.html.

Testes unitários

package com.datastructures.graphs.graphbfsdfs.classic;

import org.junit.jupiter.api.Test;

import java.util.List;
import java.util.NoSuchElementException;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class GraphTest {

    @Test
    void startsEmpty() {
        Graph<String> graph = new Graph<>();

        assertThat(graph.isEmpty()).isTrue();
        assertThat(graph.size()).isZero();
    }

    @Test
    void addVertexAddsAnIsolatedVertexWithNoEdges() {
        Graph<String> graph = new Graph<>();

        graph.addVertex("A");

        assertThat(graph.isEmpty()).isFalse();
        assertThat(graph.size()).isEqualTo(1);
        assertThat(graph.bfs("A")).containsExactly("A");
        assertThat(graph.dfs("A")).containsExactly("A");
    }

    @Test
    void addingAVertexTwiceIsANoOpAndDoesNotResetItsEdges() {
        Graph<String> graph = new Graph<>();
        graph.addEdge("A", "B");

        graph.addVertex("A");

        assertThat(graph.size()).isEqualTo(2);
        assertThat(graph.bfs("A")).containsExactlyInAnyOrder("A", "B");
    }

    @Test
    void addEdgeLinksBothVerticesInBothDirections() {
        Graph<String> graph = new Graph<>();

        graph.addEdge("A", "B");

        assertThat(graph.size()).isEqualTo(2);
        assertThat(graph.bfs("A")).containsExactly("A", "B");
        assertThat(graph.bfs("B")).containsExactly("B", "A");
    }

    @Test
    void bfsOnAnUnknownStartVertexThrows() {
        Graph<String> graph = new Graph<>();
        graph.addEdge("A", "B");

        assertThatThrownBy(() -> graph.bfs("Z"))
                .isInstanceOf(NoSuchElementException.class)
                .hasMessageContaining("Z");
    }

    @Test
    void dfsOnAnUnknownStartVertexThrows() {
        Graph<String> graph = new Graph<>();
        graph.addEdge("A", "B");

        assertThatThrownBy(() -> graph.dfs("Z"))
                .isInstanceOf(NoSuchElementException.class)
                .hasMessageContaining("Z");
    }

    /**
     * A       B
     * |\     /|
     * | \   / |
     * |  \ /  |
     * |   X   |
     * |  / \  |
     * | /   \ |
     * C ----- D    E - F (disconnected component)
     *
     * Built with a cycle (A-B-C-D-A plus both diagonals) so that both bfs and dfs are forced to
     * discard an already-visited neighbor at least once - the exact branch that only fires when
     * a vertex has more than one path leading back to it.
     */
    private Graph<String> cyclicGraphWithDisconnectedComponent() {
        Graph<String> graph = new Graph<>();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("A", "D");
        graph.addEdge("B", "C");
        graph.addEdge("B", "D");
        graph.addEdge("C", "D");
        graph.addEdge("E", "F");
        return graph;
    }

    @Test
    void bfsVisitsEveryVertexInTheConnectedComponentExactlyOnceInLayerOrder() {
        Graph<String> graph = cyclicGraphWithDisconnectedComponent();

        List<String> visitOrder = graph.bfs("A");

        assertThat(visitOrder).containsExactly("A", "B", "C", "D");
    }

    @Test
    void bfsNeverReachesADisconnectedComponent() {
        Graph<String> graph = cyclicGraphWithDisconnectedComponent();

        List<String> visitOrder = graph.bfs("A");

        assertThat(visitOrder).doesNotContain("E", "F");
    }

    @Test
    void dfsVisitsEveryVertexInTheConnectedComponentExactlyOnceInDepthFirstOrder() {
        Graph<String> graph = cyclicGraphWithDisconnectedComponent();

        List<String> visitOrder = graph.dfs("A");

        assertThat(visitOrder).containsExactly("A", "B", "C", "D");
    }

    @Test
    void dfsNeverReachesADisconnectedComponent() {
        Graph<String> graph = cyclicGraphWithDisconnectedComponent();

        List<String> visitOrder = graph.dfs("A");

        assertThat(visitOrder).doesNotContain("E", "F");
    }

    @Test
    void bfsFromTheOtherDisconnectedComponentOnlyReachesItsOwnVertices() {
        Graph<String> graph = cyclicGraphWithDisconnectedComponent();

        assertThat(graph.bfs("E")).containsExactly("E", "F");
    }

    @Test
    void dfsOnALinearChainVisitsInDepthFirstOrderNotBreadthFirstOrder() {
        Graph<String> graph = new Graph<>();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");

        List<String> visitOrder = graph.dfs("A");

        // A recursive DFS from A would go A -> B -> D (dead end, backtrack) -> C.
        assertThat(visitOrder).containsExactly("A", "B", "D", "C");
    }
}

package com.datastructures.graphs.graphbfsdfs.applied;

import org.junit.jupiter.api.Test;

import java.util.List;

import static org.assertj.core.api.Assertions.assertThat;

class AmlNetworkTraversalTest {

    @Test
    void flaggedAccountReachesEveryAccountInItsTransactionCluster() {
        AmlNetworkTraversal aml = new AmlNetworkTraversal();
        // ACC-001 (flagged) -> ACC-002 -> ACC-003, plus a direct ACC-001 -> ACC-003 shortcut.
        aml.recordTransaction("ACC-001", "ACC-002");
        aml.recordTransaction("ACC-002", "ACC-003");
        aml.recordTransaction("ACC-001", "ACC-003");

        List<String> reachable = aml.accountsReachableFrom("ACC-001");

        assertThat(reachable).containsExactlyInAnyOrder("ACC-001", "ACC-002", "ACC-003");
    }

    @Test
    void closestAccountsComeFirstInTheReachableOrder() {
        AmlNetworkTraversal aml = new AmlNetworkTraversal();
        aml.recordTransaction("ACC-001", "ACC-002");
        aml.recordTransaction("ACC-002", "ACC-003");

        List<String> reachable = aml.accountsReachableFrom("ACC-001");

        // ACC-002 is one hop away, ACC-003 is two - BFS must surface the closer one first.
        assertThat(reachable).containsExactly("ACC-001", "ACC-002", "ACC-003");
    }

    @Test
    void accountsOutsideTheFlaggedNetworkAreNeverIncluded() {
        AmlNetworkTraversal aml = new AmlNetworkTraversal();
        aml.recordTransaction("ACC-001", "ACC-002");
        // Unrelated pair of accounts transacting only with each other.
        aml.recordTransaction("ACC-100", "ACC-101");

        List<String> reachable = aml.accountsReachableFrom("ACC-001");

        assertThat(reachable).doesNotContain("ACC-100", "ACC-101");
    }
}

Ver relatório completo de cobertura JaCoCo →