Implemente um algoritmo de busca em profundidade para um grafo direcionado.
Passo 1
O que o enunciado pede e quais informações temos:
- Pedido: implementar um algoritmo de busca em profundidade para um grafo direcionado.
- Entrada esperada (informação fornecida): um grafo direcionado representando vértices e arestas; tipicamente forneceremos:
- uma lista de adjacência do grafo (para cada vértice, quais vértices saem dele);
- ou uma lista de arestas / matriz de adjacência (mas aqui vamos assumir lista de adjacência porque é a mais prática).
- Saída esperada: pelo menos a ordem de visita dos vértices (traversal), e opcionalmente:
- tempos de descoberta e finalização de cada vértice;
- árvore de pais (predecessores) da DFS;
- componentes fortemente conectadas (não exigido, só observação).
- Restrições/pressupostos que estou adotando (sem te perguntar):
- os vértices são identificados por valores inteiros ou por chaves que podem ser usadas como índices/dicionário;
- queremos uma implementação útil em prática (legível, eficiente), em Python;
- preferível suportar grafos com muitos vértices, então usaremos lista de adjacência como estrutura principal.
Passo 2
Decisão do método e representação (por que escolhi isso):
- Método: Busca em profundidade (DFS) clássica. O enunciado não impõe variação (iterativa/recursiva), então vou apresentar as duas versões:
- versão recursiva (direta, próxima da definição teórica, fácil de entender);
- versão iterativa (usando pilha explícita) — útil quando a recursão pode estourar limite de profundidade.
- Representação do grafo: lista de adjacência (um dicionário em Python que mapeia vértice -> lista de vizinhos).
- Justificativa: para grafos esparsos, lista de adjacência tem custo de memória e tempo melhor que matriz. A DFS acessa cada aresta e vértice uma vez, então lista de adjacência é natural.
- O que vamos retornar/mostrar:
- ordem de descoberta (lista com vértices na ordem em que foram descobertos);
- tempos de descoberta e finalização (opcional, mas didaticamente importante);
- array de predecessores (pai na árvore DFS), para você reconstruir a floresta gerada pela DFS.
Passo 3
Conceito e ideias fundamentais (aulas rápidas):
- Intuição da DFS: a DFS começa em um vértice, marca-o como visitado, explora um vizinho não visitado recursivamente até ir o mais fundo possível; depois volta (backtrack) e tenta outros vizinhos. Ao final, todos os vértices alcançáveis do ponto inicial terão sido visitados. Faz-se isso para cada vértice não visitado para cobrir o grafo inteiro (gera uma floresta de DFS).
- Estados clássicos para cada vértice:
- não visitado (white);
- em processamento / descoberto (gray);
- finalizado (black).
- Tempos de descoberta e finalização:
- cada vez que “descobrimos” um vértice, incrementamos um relógio e gravamos o tempo de descoberta;
- quando terminamos de processar todos os vizinhos, incrementamos o relógio e gravamos o tempo de finalização.
- Por que isso importa:
- tempos ajudam a identificar relações entre arestas (árvore, retros, forward, cross) e servem para algoritmos como detecção de ciclos, comprovação de ordenação topológica em grafos acíclicos direcionados (DAG), componentes fortemente conectadas, etc.
- Complexidade esperada:
- tempo:
, onde é número de vértices e número de arestas, porque cada vértice é processado uma vez e cada aresta é examinada uma vez; - espaço:
adicional para vetores de marcação/tempo/pai, além do espaço da representação da lista de adjacência.
- tempo:
Passo 4
Pseudocódigo de alto nível (para entender antes do código):
- Versão recursiva (esquemática):
- Inicialize arrays: visited ou color, discovery_time, finish_time, parent.
- Para cada vértice
em todos os vértices: - se
não foi visitado, chame DFS-Visit(u)
- se
- DFS-Visit(u):
- marcar
como descoberto (gray), discovery_time[u] = tempo++ - para cada v em adj[u]:
- se v não visitado:
- parent[v] = u
- DFS-Visit(v)
- se v não visitado:
- marcar
como finalizado (black), finish_time[u] = tempo++
- marcar
- Versão iterativa: usar pilha explícita simulando a recursão, mas precisamos detectar quando estamos voltando para definir finish_time — isso exige controle extra (por exemplo empilhar tuplas com estado).
Passo 5
Implementação recursiva em Python — explicando cada parte antes de mostrar o código:
- Estrutura: função principal dfs(graph) que recebe o grafo como dicionário {u: [v1, v2, …]}.
- Variáveis internas:
- color: dicionário que contém ‘white’/‘gray’/‘black’ por vértice.
- discovery, finish: dicionários com tempos.
- parent: dicionário com predecessor (ou None).
- time: contador inteiro encapsulado numa lista ou usando variável não-local.
- Comportamento:
- percorre todos os vértices do grafo (graph.keys()), chama visita recursiva se ainda for ‘white’.
- DFS-Visit atualiza tempos e estados e recursa para vizinhos não visitados.
- Observações práticas:
- ordenar vizinhos? Por vezes desejável para previsibilidade em prova; aqui não forçarei ordenação, mas posso mencionar que se precisar de ordem lexicográfica, use sorted(adj[u]).
Agora o código recursivo:
def dfs_recursive(graph):
"""
graph: dict mapping vertex -> list of neighbors (directed)
Returns:
order: list of vertices in discovery order
discovery: dict vertex -> discovery time (int)
finish: dict vertex -> finish time (int)
parent: dict vertex -> parent vertex in DFS forest (or None)
"""
color = {u: 'white' for u in graph}
discovery = {}
finish = {}
parent = {u: None for u in graph}
order = []
time = [0] # usar lista para capturar por referência na closure
def dfs_visit(u):
color[u] = 'gray'
time[0] += 1
discovery[u] = time[0]
order.append(u)
for v in graph[u]:
if color.get(v, 'white') == 'white':
parent[v] = u
dfs_visit(v)
color[u] = 'black'
time[0] += 1
finish[u] = time[0]
# Garantir que todos os vértices (mesmo isolados) aparecem em graph:
for u in list(graph):
if color[u] == 'white':
dfs_visit(u)
return order, discovery, finish, parent
Explicação linha a linha (breve):
color = {u: 'white' for u in graph}: inicializa todos como não visitados.time = [0]: usamos lista para permitir alteração dentro de dfs_visit.dfs_visit(u): quando chamado, marcaucomo ‘gray’, incrementa tempo e registradiscovery[u]. Adicionauemorder. Percorre vizinhosv; sevainda for ‘white’, gravaparent[v] = ue chamadfs_visit(v). Quando todos os vizinhos são tratados, marcaucomo ‘black’, incrementa o tempo e registrafinish[u].- No laço final, chamamos
dfs_visitpara cada vértice ainda branco para cobrir componentes desconectadas.
Passo 6
Implementação iterativa (pilha explícita) — por que e como:
- Por que usar iterativa? Em ambientes onde a recursão profunda pode estourar o limite, a versão com pilha é mais robusta. Também é útil para controle fino do retorno (momento de finalização).
- Ideia: empilhar pares (u, iterador) ou (u, estado) para saber se estamos entrando no nó pela primeira vez ou voltando depois de processar um vizinho.
- Estratégia prática usada abaixo: ao visitar um novo vértice, empilha
(u, iterator_of_adj[u]). Processamos itens do topo; quando o iterador para (exaurido), então finalizamosu.
Agora o código iterativo:
def dfs_iterative(graph):
"""
graph: dict mapping vertex -> list of neighbors (directed)
Returns: order, discovery, finish, parent (mesma semântica do dfs_recursive)
"""
color = {u: 'white' for u in graph}
discovery = {}
finish = {}
parent = {u: None for u in graph}
order = []
time = 0
for start in list(graph):
if color[start] != 'white':
continue
# pilha de tuplas: (u, iterator sobre os vizinhos)
stack = [(start, iter(graph[start]))]
color[start] = 'gray'
time += 1
discovery[start] = time
order.append(start)
while stack:
u, it = stack[-1]
try:
v = next(it)
if color.get(v, 'white') == 'white':
parent[v] = u
color[v] = 'gray'
time += 1
discovery[v] = time
order.append(v)
stack.append((v, iter(graph.get(v, []))))
except StopIteration:
# acabou os vizinhos de u
stack.pop()
color[u] = 'black'
time += 1
finish[u] = time
return order, discovery, finish, parent
Explicação prática:
- Cada entrada da pilha guarda um iterador sobre os vizinhos para que, ao retornar ao vértice, a iteração continue de onde parou (simula o retorno recursivo).
- Quando
next(it)lançaStopIteration, significa que todos os vizinhos foram processados e podemos finalizaru.
Passo 7
Complexidade e propriedades que vão cair na prova:
- Tempo:
. Justificativa: cada vértice é descoberto exatamente uma vez; para cada vértice, o laço sobre seus vizinhos examina cada aresta de saída uma vez. Assim o total de operações relacionadas às arestas é e às vértices é , então somando dá . - Espaço extra:
para arrays color/discovery/finish/parent e pilha recursiva/iterativa no pior caso (profundidade ). - A DFS produz uma floresta de DFS (um conjunto de árvores). O vetor
parentpermite reconstruir essa floresta. - Tempos de descoberta/finish podem ser usados para:
- detectar ciclos (em digraph, se existe aresta u->v com color[v] = ‘gray’ então há ciclo — aresta de retorno);
- ordenação topológica: em DAG, ordenar vértices por tempo de finalização decrescente dá uma ordenação topológica.
- Dica de prova: ao descrever o algoritmo, explique por que cada aresta é examinada a uma única vez (por causa do teste de cor) — isso é importante para justificar
.
Passo 8
Exemplo pequeno para testar mentalmente (você pode passar pelo seu caderno):
- Suponha grafo dirigido com adjacência:
- A: [B, C]
- B: [D]
- C: [E]
- D: []
- E: [B]
- Se iniciar em A, a DFS recursiva pode descobrir na ordem: A, B, D, C, E (dependendo da ordem dos vizinhos). Os tempos discovery/finish vão refletir a entrada/saída de cada nó conforme o relógio.
Passo 9
Dicas para a prova (práticas e de escrita):
- Ao explicar a DFS na prova:
- desenhe a lista de adjacência e mostre o fluxo de chamada recursiva para um exemplo pequeno;
- escreva claramente as inicializações (todos brancos, tempo = 0);
- justifique complexidade mencionando que cada aresta é verificada no máximo uma vez.
- Se pedir “ordenar topologicamente”, diga: executar DFS e então ordenar vértices por tempo de finalização decrescente.
- Se seu professor espera pseudocódigo, adapte o código acima para pseudocódigo em linhas e explique a semântica de cada linha.
Resposta
def dfs_recursive(graph):
"""
graph: dict mapping vertex -> list of neighbors (directed)
Returns:
order: list of vertices in discovery order
discovery: dict vertex -> discovery time (int)
finish: dict vertex -> finish time (int)
parent: dict vertex -> parent vertex in DFS forest (or None)
"""
color = {u: 'white' for u in graph}
discovery = {}
finish = {}
parent = {u: None for u in graph}
order = []
time = [0]
def dfs_visit(u):
color[u] = 'gray'
time[0] += 1
discovery[u] = time[0]
order.append(u)
for v in graph[u]:
if color.get(v, 'white') == 'white':
parent[v] = u
dfs_visit(v)
color[u] = 'black'
time[0] += 1
finish[u] = time[0]
for u in list(graph):
if color[u] == 'white':
dfs_visit(u)
return order, discovery, finish, parent
def dfs_iterative(graph):
"""
graph: dict mapping vertex -> list of neighbors (directed)
Returns: order, discovery, finish, parent (mesma semântica do dfs_recursive)
"""
color = {u: 'white' for u in graph}
discovery = {}
finish = {}
parent = {u: None for u in graph}
order = []
time = 0
for start in list(graph):
if color[start] != 'white':
continue
stack = [(start, iter(graph[start]))]
color[start] = 'gray'
time += 1
discovery[start] = time
order.append(start)
while stack:
u, it = stack[-1]
try:
v = next(it)
if color.get(v, 'white') == 'white':
parent[v] = u
color[v] = 'gray'
time += 1
discovery[v] = time
order.append(v)
stack.append((v, iter(graph.get(v, []))))
except StopIteration:
stack.pop()
color[u] = 'black'
time += 1
finish[u] = time
return order, discovery, finish, parent