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

Metáfora e Motivação

Grafos modelam relacionamentos (arestas) entre objetos (nós ou vértices). São onipresentes em computação, desde mapas até redes sociais. Pensar em uma cidade com ruas e cruzamentos é uma ótima metáfora: vértices são cruzamentos, arestas são ruas.

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.

Exercício Prático Guiado

  1. Modele um grafo não direcionado simples usando lista de adjacência.
  2. Implemente BFS e DFS a partir de um vértice fonte.
  3. Use essas funções para resolver o problema de Componentes Conexos (Beecrowd 1082).

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