Grafos, DFS e BFS

Representa pelo uso

$G=(V,E)$ com vértices e ligações. Dirigido distingue u->v de v->u. Simples proíbe laços e paralelas.

Precisas de	Escolhe
Teste de aresta $O(1)$ e grafo denso	Matriz $\Theta(V^2)$
Percurso linear em grafo esparso	Listas $\Theta(V+E)$
Enumerar vizinhos de u	Listas em $\Theta(\deg)$

Não dirigido guarda cada aresta duas vezes. Soma dos graus vale $2|E|$. Árvore com n tem n-1 arestas.

DFS marca cedo

Marca na descoberta, antes de explorar. Visita os alcançáveis da origem. Repete em cada por visitar para cobrir componentes.

• Pilha de chamadas guarda o caminho suspenso. Pode chegar a $O(V)$.
• Ordem depende de origem e vizinhos. Iterativa simples pode divergir da recursiva.

BFS dá distâncias

1. Origem com distância zero na fila.
2. Retira u; vizinho novo recebe dist+1 e entra na fila.
3. Marca ao inserir, não ao retirar.

A fila sai por distâncias crescentes, logo a primeira chegada é mínima em arestas. Pesos diferentes pedem outro algoritmo.

Com origem 0, camadas {0}, {1,2}, {3}, {4} e distâncias [0,1,1,2,3,ausente]. Custa $O(V+E)$ com auxiliar $O(V)$.

Contagens e cores

• Arestas de componente: soma graus dos visitados e divide por dois.
• Até distância d: BFS sem expandir a camada d, origem excluída. Reinicia estados entre chamadas.
• Bipartido: colore por camadas em todas as componentes. Aresta igual revela ciclo ímpar.

Traços completos.