6. Aplicações I
- Por que a DFS é uma ferramenta natural para detectar ciclos
- Como arestas de retorno caracterizam ciclos direcionados
- Como testar se um grafo é um DAG
- Por que os tempos de finalização sugerem uma ordenação
- Como construir ordenação topológica usando DFS
- Por que ordenação topológica só funciona em DAGs
- Casos de uso em engenharia para ordenação por dependência
A Busca em Profundidade não é apenas um método de travessia. Ela é uma ferramenta estrutural que permite duas aplicações clássicas: detecção de ciclos e ordenação topológica.
6.1 Por que DFS Detecta Ciclos
A DFS explora o grafo recursivamente e mantém controle dos vértices que estão ativos na pilha de recursão.
Se durante a exploração a DFS alcançar um vértice que já está ativo, então a busca retornou a um ancestral.
6.2 Arestas de Retorno e Ciclos
Uma aresta de retorno é uma aresta que conecta um vértice a um de seus ancestrais na árvore DFS.
6.3 Teste Prático com Cores
- WHITE — não visitado
- GRAY — ativo na recursão
- BLACK — totalmente explorado
Se durante a exploração uma aresta aponta para um vértice GRAY, então existe um ciclo.
6.4 Esboço de Algoritmo para Detectar Ciclos
HAS-CYCLE(G):
for each vertex u in V[G]:
color[u] = WHITE
for each vertex u in V[G]:
if color[u] == WHITE:
if DFS-CYCLE-VISIT(G, u):
return true
return false
6.5 Grafos DAG
Um DAG é um Directed Acyclic Graph (grafo direcionado acíclico).
6.6 Ideia da Ordenação Topológica
Uma ordenação topológica é uma ordenação linear dos vértices tal que para toda aresta (u,v), o vértice u aparece antes de v.
6.7 Regra dos Tempos de Finalização
Se ordenarmos os vértices por tempo de finalização decrescente, obtemos uma ordenação topológica.
6.8 Algoritmo de Ordenação Topológica
TOPOLOGICAL-SORT(G):
run DFS(G)
return vertices sorted by decreasing finish time
6.9 Casos de Uso em Engenharia
- ordenação de tarefas com dependências
- sistemas de build
- ordenação de disciplinas com pré-requisitos
- pipelines de processamento
6.10 Mini Resumo
- Arestas de retorno indicam ciclos.
- Ausência de arestas de retorno ⇒ DAG.
- Tempos de finalização produzem ordenação topológica.