Grafos, DFS e BFS

Imagina um mapa de cidades ligadas por estradas: cada cidade é um vértice e cada estrada é uma aresta. O conjunto das cidades e das estradas é um grafo, que se escreve $G=(V,E)$, com $V$ o conjunto de vértices e $E$ o das arestas.

Em grafos dirigidos, u->v não implica v->u. Em grafos não dirigidos, uma aresta liga os dois sentidos. Um grafo simples não tem laços nem arestas paralelas. Indica quais destas condições assumes antes de contares graus ou detetares ciclos. Esta página fixa representações e travessias; a seguinte usa-as para ciclos, ordem e conetividade.

Caminhos, graus e tipos de grafos

O grau de um vértice não dirigido conta as arestas incidentes; um laço conta duas vezes. Num grafo dirigido, distingue grau de entrada, arcos que chegam, de grau de saída, arcos que partem. A soma dos graus num grafo não dirigido é $2|E|$, porque cada aresta contribui nas duas extremidades. Num dirigido, a soma dos graus de entrada e a soma dos graus de saída valem ambas $|E|$.

Um caminho segue arestas entre vértices, respeitando os sentidos quando existem. Aqui os caminhos não repetem vértices; num ciclo, só o primeiro e o último coincidem. O comprimento conta arestas, não vértices: 0,1,3,4 tem comprimento 3. Em grafos com pesos, o custo é a soma desses pesos. A distância é o menor comprimento, ou o menor custo no contrato com pesos.

Um grafo completo simples não dirigido com n vértices tem uma aresta para cada par distinto, logo $n(n-1)/2$ arestas. Um subgrafo conserva alguns vértices e algumas arestas entre eles; uma clique é um subgrafo completo. Uma árvore, como grafo não dirigido, é conexa e sem ciclos, e tem n-1 arestas para n>=1. Esta definição não escolhe uma raiz nem uma ordem para os filhos; uma árvore binária acrescenta essas convenções. Uma floresta é um conjunto de árvores desconexas, incluindo vértices isolados.

Um grafo bipartido permite separar vértices em dois conjuntos, com cada aresta entre conjuntos diferentes. Não exige que existam todas as ligações possíveis entre os conjuntos. Um quadrado é bipartido; um triângulo não é, porque alternar lados ao longo das três arestas põe o vértice inicial nos dois lados.

Representação e custo

Nos custos seguintes, usamos V e E também para as quantidades $|V|$ e $|E|$. Um grafo esparso tem poucas arestas em relação aos pares possíveis; num denso, esse número é da ordem do quadrado do número de vértices.

Numa matriz de adjacência, guarda uma posição para cada par de vértices. Memória $\Theta(V^2)$; testar ou alterar uma aresta custa $O(1)$, mas enumerar os vizinhos de um vértice custa $\Theta(V)$. Uma matriz booleana não representa diretamente multiplicidades.

Numa lista de adjacência, cada vértice guarda os vizinhos existentes. No grafo do exemplo, com arestas 0-1,0-2,1-3,2-3,3-4, as listas são 0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3] e 5:[]; a matriz tem 1 nessas posições e 0 nas restantes. A memória das listas é $\Theta(V+E)$; um grafo não dirigido guarda cada aresta nas duas listas. Enumerar vizinhos custa $\Theta(\deg(u))$; testar ou remover uma aresta numa lista simples pode exigir um percurso desses vizinhos. Num grafo dirigido, as listas de saída não dão imediatamente todas as arestas de entrada.

Um percurso que visita todos os vértices e todas as listas custa $\Theta(V+E)$. Com matriz, custa $\Theta(V^2)$. Estas expressões incluem vértices isolados: dizer apenas $O(E)$ não cobre um grafo sem arestas.

Com V=10000 e E=10000, o grafo é esparso: há apenas uma quantidade linear de arestas, contra quase cinquenta milhões de pares não dirigidos possíveis. A matriz reserva cem milhões de células, enquanto as listas guardam dez mil cabeças e vinte mil entradas de vizinhos. Num grafo denso, tanto listas como matriz podem exigir $\Theta(V^2)$ de memória e de percurso. A vantagem assintótica das listas depende da densidade; remover uma aresta dada por dois vértices favorece a matriz, pois não precisa de procurar o destino numa lista.

DFS e a floresta de pesquisa

A pesquisa em profundidade, DFS, marca um vértice e visita recursivamente cada vizinho ainda não marcado. Marca antes de explorares as arestas para não voltares a entrar no mesmo vértice num ciclo. A pilha de chamadas conserva o caminho de tarefas suspensas.

O invariante diz que cada vértice marcado foi alcançado por um caminho da origem, e cada chamada explora as arestas do seu vértice. Se existir um caminho até um vértice não visitado no fim, nesse caminho existe uma primeira aresta de visitado para não visitado; a DFS teria seguido essa aresta, uma contradição. Logo visita exatamente os alcançáveis.

Uma DFS a partir de uma origem não percorre necessariamente todo o grafo. Para construíres uma floresta, percorre todos os vértices e começa uma DFS em cada um ainda não visitado. Num grafo não dirigido, cada nova raiz identifica uma componente conexa. Num grafo dirigido, as raízes desta floresta não contam componentes fortemente conexas.

Com origem 0 e vizinhos por ordem crescente, a DFS visita 0,1,3,2,4 e depois 5 numa segunda raiz; regista entrada e saída de cada chamada para reproduzir tempos. A ordem depende da origem e da ordem dos vizinhos. Uma versão iterativa com uma pilha de vértices pode produzir uma ordem diferente da recursiva; para reproduzires exatamente tempos de entrada e saída, guarda também a posição do próximo vizinho a explorar.

BFS por camadas

A pesquisa em largura, BFS, usa uma fila. A origem tem distância zero; ao descobrires um vizinho ainda não visitado, atribui-lhe dist[u]+1, guarda u como pai e insere-o na fila. Marca-o no momento da inserção, para que duas arestas não o insiram várias vezes.

Partindo de 0, a BFS descobre 0,1,2,3,4; 5 fica inacessível. As camadas são {0}, {1,2}, {3} e {4}. O pai de 3 é 1 porque 1 é processado antes de 2; existe também um caminho mínimo por 2.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
int main() {
    std::vector<std::vector<int>> g{{1,2},{0,3},{0,3},{1,2,4},{3},{}};
    std::vector<int> dist(g.size(), -1), pai(g.size(), -1);
    std::queue<int> q; dist[0] = 0; q.push(0);
    while (!q.empty()) {
        const int u = q.front(); q.pop();
        for (int v : g[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1; pai[v] = u; q.push(v);
        }
    }
    for (std::size_t i = 0; i < dist.size(); ++i)
        std::cout << (i ? " " : "") << dist[i];
    std::cout << '\n';
    std::vector<int> caminho;
    for (int v = 4; v != -1; v = pai[v]) caminho.push_back(v);
    std::reverse(caminho.begin(), caminho.end());
    for (std::size_t i = 0; i < caminho.size(); ++i)
        std::cout << (i ? " " : "") << caminho[i];
    std::cout << '\n';
}

A origem tem de ser um índice válido; num grafo vazio não podes atribuir dist[0]. O exemplo usa seis vértices e origem 0, com -1 para distância ainda desconhecida e pai inexistente. Antes de reconstruíres um caminho para um destino, verifica dist[destino]!=-1, porque seguir apenas o pai de um destino inacessível produziria uma lista com o destino e não um caminho válido.

Porque BFS encontra distâncias mínimas

Se um vértice descoberto com distância d+1 tivesse um caminho mais curto, o seu predecessor nesse caminho teria distância no máximo d-1 e teria sido processado antes. Esse predecessor já o teria descoberto com uma distância menor, contradizendo a primeira descoberta. Portanto a distância registada é o menor número de arestas.

O argumento exige arestas com o mesmo custo. Com A->B de peso 10, A->C de peso 1 e C->B de peso 1, BFS prefere a aresta direta por usar menos arestas, apesar de o caminho via C ter peso total 2. Um problema com pesos diferentes exige outro algoritmo; não reutilizes a prova de BFS.

Tempo $O(V+E)$ com listas; vetores de distância, pais e visitados ocupam $O(V)$, e a fila também pode atingir $O(V)$. DFS recursiva pode ter profundidade $O(V)$, mesmo num grafo esparso.

Contar arestas e vizinhos próximos

Numa componente não dirigida, contar apenas as descobertas DFS conta arestas da árvore de pesquisa, não todas as arestas da componente. Um triângulo descobre dois vértices novos a partir da raiz, mas tem três arestas. Soma antes os comprimentos das listas de todos os vértices alcançados e divide por dois: cada aresta aparece nas duas extremidades.

Para contar outros vértices a distância no máximo d da origem, usa BFS. Marca a origem com zero, mas não a acrescentes à contagem. Cada vizinho descoberto recebe a distância do pai mais um e conta uma vez. Quando retiras um vértice à distância d, não explores os seus vizinhos: ficariam para lá do limite. Com d<=0, o resultado é zero, porque a origem está excluída.

#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using Grafo = std::vector<std::vector<int>>;
// Grafo simples, nao dirigido; cada aresta ocorre nas duas listas.
long long somarGraus(const Grafo& g, int u, std::vector<bool>& visto) {
    visto[u] = true;
    long long total = static_cast<long long>(g[u].size());
    for (int v : g[u]) if (!visto[v]) total += somarGraus(g, v, visto);
    return total;
}
long long arestasComponente(const Grafo& g, int origem) {
    assert(origem >= 0 && static_cast<std::size_t>(origem) < g.size());
    std::vector<bool> visto(g.size(), false);
    return somarGraus(g, origem, visto) / 2;
}
int proximos(const Grafo& g, int origem, int limite) {
    assert(origem >= 0 && static_cast<std::size_t>(origem) < g.size());
    if (limite <= 0) return 0;
    std::vector<int> dist(g.size(), -1);
    std::queue<int> fila;
    dist[origem] = 0;
    fila.push(origem);
    int total = 0;
    while (!fila.empty()) {
        const int u = fila.front(); fila.pop();
        if (dist[u] == limite) continue;
        for (int v : g[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            ++total;
            fila.push(v);
        }
    }
    return total;
}
int main() {
    const Grafo g{{1,2},{0,2},{0,1,3},{2},{5},{4},{}};
    std::cout << "arestas: " << arestasComponente(g,0) << ' '
              << arestasComponente(g,4) << ' ' << arestasComponente(g,6) << '\n';
    for (int d : {0,1,2,99}) std::cout << "raio " << d << ": " << proximos(g,0,d) << '\n';
    return 0;
}

O grafo tem um triângulo 0-1-2-0 e a aresta 2-3, outra componente 4-5 e o isolado 6. As contagens de arestas são 4, 1 e 0. Desde 0, os raios 0, 1, 2 e 99 contêm respetivamente 0, 2, 3 e 3 outros vértices. Os raios grandes não incluem componentes inacessíveis.

As duas funções criam visitados ou distâncias de novo, pelo que chamadas consecutivas não misturam resultados. Com listas, o limite geral é $O(V+E)$, incluindo inicializar o vetor de tamanho V; podar a BFS poupa a exploração para lá do raio, mas não elimina essa inicialização. A DFS conta toda a componente, e a pilha pode atingir $O(V)$. Este programa exige origem válida, destinos válidos e grafo simples não dirigido com listas simétricas.

Bipartição e grelhas

Para bipartição, colore a origem com 0 e cada vizinho com a cor oposta durante a BFS; um conflito de cores prova um ciclo ímpar. Numa grelha, a fila guarda pares (linha,coluna) e verifica fronteiras e obstáculos antes de inserir. Começar com várias origens a distância zero dá a distância à origem mais próxima, como na nuvem de cinza do exercício AED070 (2025/26).

Caminhos, diâmetro e grafos implícitos

A árvore de pais de BFS fornece um caminho mínimo por destino, não todos os caminhos mínimos. No exercício AED069 (2025/26), o desempate compara caminhos a partir do destino e equivale a escolher sempre o menor predecessor; é um contrato particular desse enunciado, não uma regra geral de ordem lexicográfica a partir da origem.

A distância de uma origem a si própria é zero. Num grafo não dirigido conexo, o diâmetro é a maior distância mínima entre pares, e repetir BFS de cada origem calcula-o em $O(V(V+E))$; num grafo desconexo tens de definir se consideras diâmetro infinito, por componente, ou se o problema exclui esse caso.

Numa grelha, os vértices podem ser posições livres e os vizinhos podem ser calculados a partir dos quatro movimentos, sem construir todas as listas. Verifica fronteiras e obstáculos antes de descobrires uma posição. Se o estado inclui uma chave recolhida, orientação ou outro recurso, só a posição não chega: visitados e distância devem identificar o estado completo.

BFS com várias origens começa com todas as origens na fila a distância zero. O mesmo argumento por camadas dá a distância à origem mais próxima. Não é preciso executares uma BFS separada para cada origem.