Resumo para Prova de Algoritmos em Grafos
Tema Principal: Percurso em Profundidade (DFS) e Ordenação Topológica
1. Conceitos Básicos
Grafo Direcionado Acíclico (DAG)
•Definição: Um grafo direcionado sem ciclos.
•Aplicações: Representa relações de precedência (ex: dependências entre tarefas, pré-
requisitos em cursos).
•Teorema Importante:
•Todo DAG possui pelo menos uma fonte (vértice com grau de entrada zero) e
um sumidouro (vértice com grau de saída zero).
•Por que isso importa? Fontes e sumidouros são essenciais para algoritmos de
ordenação topológica.
Fecho Transitivo
•Definição: Extensão de um DAG onde toda relação de alcançabilidade é explicitada por
arestas diretas.
uv
•Exemplo: Se u alcança v, adiciona-se a aresta uv no fecho transitivo.
v
2. Busca em Profundidade (DFS)
Objetivo
Explorar todos os vértices de um grafo seguindo um caminho até o fim antes de
retroceder (como labirintos).
Passos do Algoritmo
[Link] dos Vértices:
•Branco: Não visitado.
•Cinza: Visitado, mas ainda explorando vizinhos.
•Preto: Completamente explorado.
[Link]: Usada para rastrear o caminho atual.
nO
m
[Link]: O(n+m), onde n= vértices e m= arestas.
(
=
Implementação
n
+ Principal: Inicializa todas as marcas como branco.
•DFS
m
•Procedimento Visita: Explora recursivamente os vizinhos de um vértice, marcando-os
)
como cinza e depois preto.
Exemplo Prático (Cormen et al., Cap. 22):
Imagine explorar uma árvore genealógica: você vai até o ancestral mais distante antes de
voltar para explorar outros ramos.
3. Ordenação Topológica
Definição
uv
•Uma ordenação linear dos vértices de um DAG onde toda aresta uv implica
v
que u aparece antes de v.
•Aplicações: Agendar tarefas com dependências, compilar módulos de software.
Algoritmo via DFS
[Link] o DFS no DAG.
[Link] marcar um vértice como preto, insira-o no início de uma lista.
3.A lista resultante é uma ordenação topológica.
Exemplo Intuitivo (Szwarcfter, Cap. 4):
Pense em vestir-se:
•Ordem correta: Meias → Calçados; Cueca → Calça → Cinto → Camisa → Gravata →
Paletó.
•Errado: Colocar os sapatos antes das meias gera inconsistência.
Propriedades
•Não é única: Um DAG pode ter múltiplas ordenações válidas.
O
•Complexidade: O(n+m), igual ao DFS.
(
n
4.
+ Relação entre DFS e Ordenação Topológica
m
) que o DFS funciona?
•Por
•Ao marcar um vértice como preto, garantimos que todos os seus sucessores já
foram processados.
•Isso garante a ordem correta das dependências.
Dica de Estudo (Cormen et al., Seção 22.4):
•Desenhe um DAG simples (ex: tarefas A → B → C) e simule o DFS para ver a ordenação
resultante.
5. Pontos de Atenção
Armadilhas Comuns
•Ciclos no Grafo: Se o grafo tem ciclos, não é um DAG, e a ordenação topológica é
impossível.
•Implementação Recursiva: Entenda bem a pilha implícita do DFS para evitar erros.
Dicas para a Prova
[Link] Grafos: Pratique ordenações topológicas manualmente em DAGs.
[Link] o Teorema: Saiba provar que todo DAG tem fonte e sumidouro (argumento
por contradição com ciclos).
[Link] com BFS: DFS é para ordenação topológica; BFS é para caminhos mais curtos.
6. Referências Cruzadas
•Cormen et al.:
•DFS: Cap. 22.3.
•Ordenação Topológica: Cap. 22.4.
•Szwarcfter:
•Algoritmos para DAGs: Cap. 4.
