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: O(V+E), onde V é número de vértices e E número de arestas, porque cada vértice é processado uma vez e cada aresta é examinada uma vez;
    • espaço: O(V) adicional para vetores de marcação/tempo/pai, além do espaço da representação da lista de adjacência.

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 u em todos os vértices:
      • se u não foi visitado, chame DFS-Visit(u)
    • DFS-Visit(u):
      • marcar u como descoberto (gray), discovery_time[u] = tempo++
      • para cada v em adj[u]:
        • se v não visitado:
          • parent[v] = u
          • DFS-Visit(v)
      • marcar u como finalizado (black), finish_time[u] = tempo++
  • 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, marca u como ‘gray’, incrementa tempo e registra discovery[u]. Adiciona u em order. Percorre vizinhos v; se v ainda for ‘white’, grava parent[v] = u e chama dfs_visit(v). Quando todos os vizinhos são tratados, marca u como ‘black’, incrementa o tempo e registra finish[u].
  • No laço final, chamamos dfs_visit para 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 finalizamos u.
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ça StopIteration, significa que todos os vizinhos foram processados e podemos finalizar u.

Passo 7

Complexidade e propriedades que vão cair na prova:
  • Tempo: O(V+E). 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 é O(E) e às vértices é O(V), então somando dá O(V+E).
  • Espaço extra: O(V) para arrays color/discovery/finish/parent e pilha recursiva/iterativa no pior caso (profundidade O(V)).
  • A DFS produz uma floresta de DFS (um conjunto de árvores). O vetor parent permite 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 O(V+E).

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

Exercícios relacionados