Grafos: Representação e Travessia (BFS/DFS)

Metáfora e Motivação

Grafos modelam relacionamentos (arestas - edges) entre objetos (nós ou vértices - vertices). Eles formam o coração de gigantes computacionais modernos, desde modelagem de tráfego aéreo até sistemas de amizades em Redes Sociais. Uma abstração simples: Pense numa cidade. Os vértices são os cruzamentos, e as arestas são as ruas que os interligam. Se a rua tem mão única, chamamos a aresta de direcionada (directed), caso contrário bi-direcionada (undirected). Se o trajeto gasta combustível ou tem pedágio, é um grafo com peso.

Introdução Teórica às Representações

Como falar ao computador que certas bolinhas se ligam umas às outras? Existem dois moldes principais em código:

1. Matriz de Adjacência

Matriz quadrada dimensional \(V \times V\) onde \(M[i][j] = 1\) se existe uma ligação direta entre o nó i e o nó j. * Vantagens: É instantâneo verificar “Existe rua entre X e Y?”. Você acessa explicitamente via indicação if(M[x][y]) respondendo em \(\mathbf{O(1)}\). * Desvantagens: O desperdício espacial! Em malhas difusas, matrizes gigantes cheias de zeros alocam desnecessariamente \(\mathbf{O(V^2)}\) memória.

2. Lista de Adjacência (Padrão em Torneios)

Vetor contendo Listas (normalmente o clássico vector<vector<int>> em C++). Na gaveta do vetor correspondente ao índice \(i\), empilhamos quais outros vizinhos ele consegue enxergar diretamente. * Vantagens: Compressão altíssima. Você gasta localmente memória correspondente as exatas ligações elásticas em uso \(\mathbf{O(V+E)}\). * Desvantagens: Para checar se \(i\) cruza com \(j\), é preciso procurar na lista inteira de \(i\), iterando \(\mathbf{O(Grau(i))}\).

Travessias: Visitando os Vizinhos

BFS (Busca em Largura)

A fila do supermercado (std::queue).
Opera num mecanismo de Onda ou Camadas propagatórias, mapeando perfeitamente a distância de saltos. Analisa todos os filhos primeiro, pra depois analisar os netos.
Mágica Prática: Encontra categoricamente o percurso mais curto num grafo não pavimentado (sem pesos).

DFS (Busca em Profundidade)

O Desbravador de Labirintos (std::stack ou recursão nativa).
Mergulha o mais rápido e profundo num cano até um fundo cego, não deu em nada? Retrocede pro entroncamento anterior (Backtracking).
Mágica Prática: Excelente para pinçar Ciclos infinitos no grafo, classificar Componentes fortemente conexos através das famosas funções temporais de visita (Tarjan) e Ordenações Topológicas (Topological Sort).

A Prática: Contando Camadas com BFS

O problema fundamental do BFS ressalta calcular o número de arestas mínimas da bolinha X até a bolinha Y.

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

// BFS Clássica usando Lista de Adjacência
int distanciaMinima(int V, vector<vector<int>>& grafo, int inicio, int destino) {
    // Vetor de rastreio contendo distâncias pré-limpas
    vector<int> distancias(V, -1); 
    
    queue<int> fila;
    fila.push(inicio);
    distancias[inicio] = 0; // Distância pra mim mesmo é 0

    // Envolvendo propagação em O(V + E)
    while(!fila.empty()) {
        int atual = fila.front();
        fila.pop();

        if (atual == destino) return distancias[atual]; // Bateu na meta!

        // Visitar os vizinhos imediatamente conectados...
        for(int vizinho : grafo[atual]) {
            if(distancias[vizinho] == -1) { // Só toco nos intocados
                distancias[vizinho] = distancias[atual] + 1; // Camada superior
                fila.push(vizinho);
            }
        }
    }
    return -1; // Desconectado / Impossível chegar
}

void executando_testes() {
    int V = 5;
    vector<vector<int>> adj(V);
    
    // Modelando o exato grafo Mermaid mostrado acima na Metáfora
    // Ligações: 0-1, 0-2, 1-3, 2-3, 3-4.  0(A) querendo chegar em 4(E)
    adj[0] = {1, 2};
    adj[1] = {0, 3};
    adj[2] = {0, 3};
    adj[3] = {1, 2, 4};
    adj[4] = {3};

    // Pelo Mermaid, passando de A para C para D para E são 3 links! Ou A -> B -> D -> E (3 tbm).
    assert(distanciaMinima(V, adj, 0, 4) == 3);
    assert(distanciaMinima(V, adj, 1, 2) == 2); // B(1) vai pra A(0) vai pra C(2) = 2 saltos
    assert(distanciaMinima(V, adj, 0, 0) == 0); // Para ele mesmo

    cout << "[✅] Testes BFS validados com sucesso em saltos predefinidos.\n";
}

int main() {
    executando_testes();
    return 0;
}

Exercício Guiado (Identificando Ilhas/Componentes)

Problema: Beecrowd 1082 - Componentes Conexos Dada uma região metropolitana desfigurada, ache e conte quantos “arquipélagos” desvinculados um do outro existem, ou seja, onde a BFS trava pois não consegue atingir nenhum território a nado.

Raciocínio: Crie um array global visitados[N]. Itere os vértices via um for(0 -> N-1). Repentinamente, você viu um índice não visitado? Opa, se ninguém o pintou antes em propagações passadas, acabamos de aterrissar desbravando um novo Continente Conexo isolado! Dispare uma simples DFS() cega puramente em cima dele apenas para ele infestar os arredores e pintar geograficamente todos daquela tribo. Incremente sua variável ilhas_descobertas = ilhas_descobertas + 1. Avance no laço. Ao terminar os for, sua contagem traduz todos os agrupamentos do país isolados individualmente.

Listagem de Exercícios Complementares

A consolidação de Travessia e Componentização requer muita repetição motora para internalizar as entranhas recursivas das DFS. Teste-as neste rol de referências: