1. O Desafio de Percorrer Redes com Ciclos e o Vetor de Visitados

Na Aula 42, percorremos árvores com facilidade porque elas nunca possuem ciclos: basta descer da raiz até as folhas. Em um Grafo arbitrário, porém, existe um perigo letal:

O vértice A conecta-se a B, B conecta-se a C, e C conecta-se de volta a A! Se você navegar sem proteção, o programa entrará em um laço infinito perpétuo.

A solução universal é o Vetor de Visitados (Visited Array): mantemos uma tabela lógica onde visitados[v] = falso no início. Assim que colocamos os pés em um vértice, marcamos visitados[v] = verdadeiro. Vizinhos que já estão marcados como visitados são sumariamente ignorados.

2. Busca em Largura (BFS): Ondas Concêntricas e Filas FIFO

A Busca em Largura (BFS - Breadth-First Search) explora o grafo em ondas concêntricas homogêneas, como uma pedra lançada em um lago calmo:

  • Camada 0: O vértice de partida.
  • Camada 1: Todos os vizinhos diretos imediatos a 1 salto de distância.
  • Camada 2: Todos os vizinhos dos vizinhos a 2 saltos de distância.

Para garantir que nenhum vértice da Camada 2 seja visitado antes de todos os da Camada 1 terem sido processados, utilizamos a disciplina FIFO da Fila (Queue).

3. A Propriedade Mágica do BFS: Menor Caminho em Número de Passos

A consequência matemática mais espetacular do BFS é o Teorema do Menor Caminho em Grafos Não-Ponderados:

Como o BFS visita todas as opções a distância 1, depois todas a distância 2, o primeiro momento em que o vértice de destino é retirado da fila corresponde matematicamente ao caminho mais curto possível até ele!

4. Implementação Completa de BFS em logicabr.dev

Vejamos a implementação de BFS calculando distâncias mínimas em número de saltos na sintaxe oficial do logicabr.dev:

Busca em Largura (BFS) com Fila em logicabr.dev logicabr.dev 
numero TOTAL_VERTICES = 5;
vetor nomesRede = ["Alice", "Bob", "Carol", "Daniel", "Eduardo"];

// Matriz de conexoes nao-direcionadas
vetor redeGrafo = [];
redeGrafo[0] = [0, 1, 1, 0, 0];  // Alice conecta com Bob e Carol
redeGrafo[1] = [1, 0, 0, 1, 0];  // Bob conecta com Alice e Daniel
redeGrafo[2] = [1, 0, 0, 0, 1];  // Carol conecta com Alice e Eduardo
redeGrafo[3] = [0, 1, 0, 0, 1];  // Daniel conecta com Bob e Eduardo
redeGrafo[4] = [0, 0, 1, 1, 0];  // Eduardo conecta com Carol e Daniel

funcao executarBFS(numero origem) {
  vetor visitados = [falso, falso, falso, falso, falso];
  vetor distancia = [-1, -1, -1, -1, -1];
  vetor filaBFS = [];
  numero inicioFila = 0;
  numero fimFila = 0;

  // Enfileira a origem
  visitados[origem] = verdadeiro;
  distancia[origem] = 0;
  filaBFS[fimFila] = origem;
  fimFila = fimFila + 1;

  saida("--- INICIANDO BFS A PARTIR DE " + nomesRede[origem] + " ---");

  enquanto (inicioFila < fimFila) {
    numero u = filaBFS[inicioFila];
    inicioFila = inicioFila + 1;

    saida("Visitando: " + nomesRede[u] + " (Distancia da origem: " + distancia[u] + " saltos)");

    // Explora todos os vizinhos de u
    para (numero v = 0; v < TOTAL_VERTICES; v++) {
      se (redeGrafo[u][v] == 1 e nao visitados[v]) {
        visitados[v] = verdadeiro;
        distancia[v] = distancia[u] + 1;
        filaBFS[fimFila] = v;
        fimFila = fimFila + 1;
      }
    }
  }
}

saida("================================================");
saida("     BUSCA EM LARGURA (BFS) logicabr.dev        ");
saida("================================================");
executarBFS(0); // Comeca por Alice
saida("================================================");

5. Busca em Profundidade (DFS): O Labirinto e a Call Stack

A Busca em Profundidade (DFS - Depth-First Search) segue uma filosofia diametralmente oposta: como um explorador cauteloso em um labirinto escuro que desenrola um fio de lã atrás de si, o algoritmo avança o mais fundo possível por um corredor até bater em um beco sem saída ou em um nó já visitado.

Nesse momento, ele recua (backtracking) até o último cruzamento com caminhos inexplorados e tenta o próximo galho.

6. Implementação Completa de DFS em logicabr.dev

Abaixo está a implementação recursiva de DFS utilizando a Call Stack da linguagem:

Busca em Profundidade (DFS) Recursiva em logicabr.dev logicabr.dev 
vetor dfsVisitados = [falso, falso, falso, falso, falso];

funcao executarDFS(numero u) {
  dfsVisitados[u] = verdadeiro;
  saida(">> [DFS ENTROU]: " + nomesRede[u]);

  para (numero v = 0; v < TOTAL_VERTICES; v++) {
    se (redeGrafo[u][v] == 1 e nao dfsVisitados[v]) {
      executarDFS(v);
    }
  }

  saida("<< [DFS RETORNOU / BACKTRACK]: " + nomesRede[u]);
}

saida("--- INICIANDO DFS A PARTIR DE ALICE ---");
executarDFS(0);

6.1 Detecção de Ciclos em Dígrafos com Coloração de 3 Estados

Uma das aplicações mais nobres do DFS é a Detecção de Ciclos em Grafos Direcionados. Como saber se há dependências circulares em um sistema de pacotes (ex: pacote A depende de B que depende de A)?

Utilizamos o algoritmo clássico de coloração de três estados:

  • Estado 0 (Branco): Vértice ainda não explorado.
  • Estado 1 (Cinza): Vértice está atualmente ativo na pilha de recursão (processamento em andamento).
  • Estado 2 (Preto): Vértice e todos os seus descendentes já foram completamente explorados.

Se durante a exploração o DFS tentar visitar um vizinho que já está marcado com Estado 1 (Cinza), encontramos uma Back-Edge (Aresta de Retorno)! Isso comprova infalivelmente a presença de um ciclo destrutivo.

Detecção de Ciclos em Dígrafos com DFS logicabr.dev 
vetor estadoCor = [0, 0, 0, 0, 0]; // 0: Branco, 1: Cinza, 2: Preto

funcao temCicloDFS(numero u) {
  estadoCor[u] = 1; // Entra na pilha (Cinza)

  para (numero v = 0; v < TOTAL_VERTICES; v++) {
    se (redeGrafo[u][v] == 1) {
      se (estadoCor[v] == 1) {
        saida("[CICLO DETECTADO]: Dependencia circular entre " + nomesRede[u] + " e " + nomesRede[v] + "!");
        retorno verdadeiro;
      }
      se (estadoCor[v] == 0 e temCicloDFS(v)) {
        retorno verdadeiro;
      }
    }
  }

  estadoCor[u] = 2; // Concluido (Preto)
  retorno falso;
}

saida("Verificando integridade acíclica do grafo: " + temCicloDFS(0));

7. Teste de Mesa Comparativo: Ordem de Visitação BFS vs DFS

Observe como a mesma rede gera ordens de visitação radicalmente distintas partindo do nó 0 (Alice):

Algoritmo Sequência de Visita dos Vértices Estrutura Central Superpoder Principal
BFS (Largura) Alice → Bob → Carol → Daniel → Eduardo Fila (Queue FIFO) Menor caminho em número de arestas
DFS (Profundidade) Alice → Bob → Daniel → Eduardo → Carol Pilha (Call Stack LIFO) Detecção de ciclos, ordenação topológica

Fundamentos de Arquitetura e Impacto no Hardware da CPU

Para compreender verdadeiramente a performance de um algoritmo em ambientes modernos, não basta analisar apenas a contagem de instruções no papel. A arquitetura dos processadores atuais (x86-64 e ARM) baseia-se em hierarquias complexas de memória: registradores ultra-rápidos, caches L1 (instruções e dados), L2, L3 e finalmente a memória RAM principal.

Quando executamos Hardware da CPU, Consumo de Memória e Linhas de Cache, o comportamento do circuito de Branch Prediction (predição de saltos condicionais) da CPU desempenha um papel determinante. Cada desvio condicional (como um comando se ou condição de laço enquanto) que não pode ser previsto com precisão pela CPU provoca uma descarga da esteira de instruções (pipeline stall), descartando ciclos preciosos de processamento.

A escolha entre BFS e DFS impacta frontalmente o consumo de memória RAM do sistema operacional. O BFS precisa armazenar em sua fila todos os vértices da camada atual simultaneamente. Em uma rede social onde cada usuário possui 500 amigos, a camada 1 tem 500 pessoas, mas a camada 2 tem até 250.000 pessoas! A fila do BFS pode facilmente consumir centenas de megabytes de RAM em poucos segundos.

O DFS, por outro lado, mantém na Call Stack apenas os nós que compõem o caminho ativo do ramo em exploração. Seu consumo de memória é proporcional apenas à profundidade máxima H do grafo O(H), que costuma ser minúscula em relação ao volume total de nós.

Do ponto de vista da física da computação, a localidade espacial e temporal de referência é outro fator crítico: percorrer a memória em posições contíguas sequenciais permite que o mecanismo de Hardware Prefetching da CPU antecipe os próximos blocos de dados antes mesmo de serem solicitados pelo código, carregando linhas inteiras de cache (tipicamente 64 bytes) sem penalidade de latência.

Demonstração Matemática Rigorosa da Eficiência Assintótica

A análise teórica desenvolvida pela ciência da computação formal permite prever o comportamento exato do algoritmo quando o volume de dados (N) cresce exponencialmente em direção ao infinito:

A complexidade formal de tempo de ambos os algoritmos em grafos representados com matriz de adjacência é Theta(V^2), pois cada linha da matriz é inspecionada para cada vértice visitado. Com listas de adjacência, ambos atingem a perfeição de Theta(V + E).

Essa dedução algébrica formal comprova por que a intuição superficial frequentemente engana programadores juniores. Saber classificar formalmente as curvas de crescimento assintótico separa o amador do engenheiro de software qualificado para arquitetar sistemas de alta escala que atendem milhões de usuários simultâneos sem lentidão.

9. Demonstração Formal: Complexidade Temporal O(V + E)

A prova de tempo linear (Theta(V + E)) para listas de adjacência baseia-se em duas verdades matemáticas:

  1. Cada vértice (u) entra na fila (BFS) ou na pilha (DFS) exatamente uma única vez, custando (Theta(V)).
  2. Para cada vértice que sai, inspecionamos apenas suas arestas incidentes ( ext{grau}(u)). A soma dos graus de todos os vértices é igual ao dobro do número de arestas: (sum ext{grau}(u) = 2E).

Portanto, o número total de operações fundamentais é rigorosamente limitado por (c_1 V + c_2 E = Theta(V + E)), tornando essas buscas assintoticamente ótimas.

10. Casos Reais: 6 Graus do LinkedIn, Web Crawlers e Deadlocks

Onde esses algoritmos sustentam a indústria moderna:

  • 6 Graus de Conexão no LinkedIn: O cálculo de "Conexão de 1º, 2º e 3º grau" é executado através de um BFS que para na terceira camada a partir do seu perfil.
  • Googlebot e Web Crawlers: O motor de busca do Google navega pela World Wide Web através de um BFS massivo, descobrindo novas páginas a partir dos links (arestas) das páginas já conhecidas.
  • Detecção de Deadlock em Sistemas Operacionais: Quando processos no Linux ou Windows competem por recursos e travam em espera mútua, o kernel roda um DFS no Grafo de Alocação de Recursos (RAG) para detectar o ciclo fechado e encerrar o processo culpado.

11. Os 5 Erros Críticos ao Implementar BFS e DFS

Evite estes erros fatais que quebram a execução de buscas:

1. Marcar como Visitado ao Desenfileirar em Vez de ao Enfileirar no BFS

Se você marcar visitados[v] = verdadeiro apenas quando o nó sai da fila, múltiplos vizinhos enfileirarão o mesmo nó repetidas vezes na mesma camada. Isso causa uma explosão combinatória de nós redundantes e esgota a memória da máquina.

2. Usar DFS Acreditando que Ele Acha o Menor Caminho

O DFS encontra um caminho, mas frequentemente encontra o caminho mais longo e tortuoso possível. Apenas o BFS garante o caminho mínimo em número de passos.

3. Estouro de Call Stack com DFS em Grafos Profundos

Em grafos com 1.000.000 de vértices dispostos em linha, a recursão causará Stack Overflow fatal. Nesses casos, deve-se implementar o DFS iterativo com uma Pilha explícita no Heap.

4. Esquecer Grafos Desconexos com Múltiplas Ilhas

Se o grafo tiver componentes desconectados (duas ilhas que não têm pontes entre si), rodar o algoritmo a partir de um único vértice deixará a outra ilha 100% inexplorada. Para explorar o grafo inteiro, deve-se iterar por todos os vértices de 0 a V-1 chamando a busca para os ainda não visitados.

5. Não Reinicializar o Vetor de Visitados Entre Consultas

Se você rodar uma segunda busca logo após a primeira sem resetar o vetor de visitados para falso, a nova busca acreditará que todos os nós já foram visitados e terminará instantaneamente sem produzir nenhum resultado.

12. Projeto Prático: Rastreador de Graus de Amizade em logicabr.dev

Vamos construir um Calculador de Graus de Separação em Rede Social demonstrando a teoria dos 6 Graus de Kevin Bacon com BFS:

Rastreador de Graus de Separação com BFS logicabr.dev 
numero QTD_MEMBROS = 5;
vetor usuarios = ["Lucas", "Mariana", "Pedro", "Julia", "Gabriel"];

// Amizades da rede
vetor amizades = [];
amizades[0] = [0, 1, 0, 0, 0];  // Lucas e amigo de Mariana
amizades[1] = [1, 0, 1, 0, 0];  // Mariana e amiga de Lucas e Pedro
amizades[2] = [0, 1, 0, 1, 0];  // Pedro e amigo de Mariana e Julia
amizades[3] = [0, 0, 1, 0, 1];  // Julia e amiga de Pedro e Gabriel
amizades[4] = [0, 0, 0, 1, 0];  // Gabriel e amigo de Julia

funcao calcularGrauSeparacao(numero userA, numero userB) {
  vetor vis = [falso, falso, falso, falso, falso];
  vetor dist = [-1, -1, -1, -1, -1];
  vetor fila = [];
  numero pIni = 0;
  numero pFim = 0;

  vis[userA] = verdadeiro;
  dist[userA] = 0;
  fila[pFim] = userA;
  pFim = pFim + 1;

  enquanto (pIni < pFim) {
    numero curr = fila[pIni];
    pIni = pIni + 1;

    se (curr == userB) {
      saida(">>> [CONEXAO ENCONTRADA]: " + usuarios[userA] + " esta a " + dist[curr] + " grau(s) de distancia de " + usuarios[userB] + "!");
      retorno dist[curr];
    }

    para (numero viz = 0; viz < QTD_MEMBROS; viz++) {
      se (amizades[curr][viz] == 1 e nao vis[viz]) {
        vis[viz] = verdadeiro;
        dist[viz] = dist[curr] + 1;
        fila[pFim] = viz;
        pFim = pFim + 1;
      }
    }
  }

  saida("[SEM CONEXAO]: Nao ha caminho social entre " + usuarios[userA] + " e " + usuarios[userB]);
  retorno -1;
}

saida("==================================================");
saida("   SIMULADOR DE GRAUS DE SEPARACAO SOCIAL         ");
saida("==================================================");

calcularGrauSeparacao(0, 1); // Lucas e Mariana (1 grau)
calcularGrauSeparacao(0, 4); // Lucas e Gabriel (4 graus de cadeia)
saida("==================================================");

Parabéns! Você concluiu a Trilha 9: Estruturas Não-Lineares, Grafos e Técnicas Algorítmicas com maestria. Na Trilha 10, entraremos na fase final de formação: os Paradigmas Algorítmicos Avançados (Gulosos, Backtracking, Programação Dinâmica) e o Projeto Integrador de Grande Porte.