Percursos e componentes em grafos

Escolher o percurso

Situação	Método	Condição	Custo
Menor número de arestas desde $s$	BFS com fila	Pesos iguais ou ignorados; marcar ao inserir	$O(n+m)$
Explorar ramos e detetar ciclos	DFS com regresso	Reiniciar em cada vértice por visitar	$O(n+m)$
Ordenar dependências	Kahn ou DFS invertida	DAG; Kahn deve emitir $n$	$O(n+m)$
Regiões mutuamente alcançáveis	Kosaraju ou Tarjan	Grafo dirigido	$O(n+m)$
Duas cores sem conflito	BFS por componente	Testar cada componente	$O(n+m)$

$n=|V|$, $m=|E|$, listas de adjacência. Memória auxiliar $O(n)$.

BFS e distâncias sem pesos

• Marca o vértice ao inserir na fila, não ao retirar.
• Na primeira descoberta, $d[v]=d[u]+1$ e pai[v]=u.
• $d[v]$ é o mínimo número de arestas desde $s$.
• Inalcançável mantém distância desconhecida, nunca zero.
• Com pesos distintos, usa caminhos mínimos.

DFS, cores e ciclos

• Branco: por descobrir. Cinzento: chamada ativa. Preto: chamada terminada.
• Aresta dirigida para cinzento fecha um ciclo; para preto não prova ciclo.
• Em grafo não dirigido, a aresta de regresso ao pai não conta. Com paralelas, distingue pelo identificador da aresta.
• Intervalos de descoberta e término disjuntos ou encaixados; contenção indica ancestralidade.
• Profundidade até $n$; em grafos grandes, a recursão pode exigir versão iterativa.

Ordem topológica

Existe se e só se o grafo dirigido não tem ciclos.

1. Kahn: fila com graus de entrada zero; emite, reduz sucessores, insere novos zeros.
2. Se emitir menos de $n$, há ciclo e a ordem parcial é inválida.
3. Alternativa: inverter términos de DFS após excluir arestas de retorno.
4. Várias ordens podem ser válidas; fila de prioridade dá a menor segundo desempate, com custo extra.

Bipartição

• BFS em cada componente com cores opostas em vizinhos.
• Aresta com cores iguais revela ciclo ímpar e rejeita.
• Bipartido exatamente quando não há ciclos ímpares.
• Árvores e ciclos pares passam; triângulos falham.

Componentes fortemente conexas

SCC é conjunto maximal com alcançabilidade mútua. Maximal não é maior tamanho.

A aresta $c\to d$ não funde SCC sem regresso. Contrair cada SCC dá um DAG.

Kosaraju:

1. DFS completa em $G$; guarda ordem de término.
2. Constrói $G^T$ com arestas invertidas.
3. DFS em $G^T$ por término decrescente; cada árvore é uma SCC.

Tarjan (uma passagem):

• low[u] é o menor índice alcançável na região ativa.
• Vizinho novo: explora e usa low[v].
• Vizinho na pilha: usa index[v].
• Vizinho fora da pilha: ignora, pertence a SCC fechada.
• low[u]==index[u] fecha SCC ao desempilhar até $u$.

Precisa de onStack, não apenas visited. A pilha de Tarjan difere da pilha de chamadas.

Provas e traços completos.