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

Introdução Teórica

Grafos modelam relacionamentos (arestas) entre objetos (nós ou vértices). São onipresentes em computação, desde mapas até redes sociais.

Representação

  1. Matriz de Adjacência: Matriz \(V \times V\) onde \(M[i][j]=1\) se existe aresta.
    • Prós: Checagem \(O(1)\). Contras: Gasta memória \(O(V^2)\), lento para iterar vizinhos \(O(V)\).
  2. Lista de Adjacência: Vetor onde cada posição \(i\) guarda uma lista dos vizinhos de \(i\).
    • Prós: Memória \(O(V+E)\), iterar vizinhos é proporcional ao grau do nó. Padrão em competições.

Travessias

  • BFS (Busca em Largura): Usa uma Fila. Explora em camadas. Garante o menor caminho em grafos sem peso (menor número de arestas).
  • DFS (Busca em Profundidade): Usa uma Pilha (ou recursão). Vai o mais fundo possível e backtrack. Útil para detectar ciclos, componentes conexos e ordenação topológica.

Problema Clássico

Problema: Componentes Conexos Link: Beecrowd 1082

Descrição: Dado um grafo não direcionado com letras como vértices, imprimir todos os componentes conexos (grupos de vértices interligados) e o número total de componentes.

Solução: Iterar de ‘a’ a ‘z’. Se um vértice não foi visitado, ele inicia um novo componente. Chame uma DFS ou BFS a partir dele para marcar e listar todos os vértices pertencentes a esse componente.

Variações e Exercícios

  1. [Coloração de Cenários (Flood Fill)]
    • Foco: Usar BFS/DFS para preencher áreas em uma matriz (grid implícito). O “labirinto” é um grafo onde cada célula \((r, c)\) conecta em vizinhos.
    • Link: Beecrowd 1907
  2. [Desenhando Labirintos]
    • Foco: DFS contando arestas (travessia completa).
    • Link: Beecrowd 1076
  3. [Famílias de Troia]
    • Foco: Outro problema clássico de componentes conexos.
    • Link: Beecrowd 2440
Back to top