Algoritmos de busca em profundidade (DFS)

7.1 Princípios do funcionamento do algoritmo DFS

Busca em profundidade (Depth-First Search, DFS) — é um algoritmo de travessia ou busca em um grafo. Ele começa com um vértice inicial e vai fundo no grafo até alcançar um vértice sem vizinhos não visitados, então retorna e continua o processo com outros vértices.

Passos do algoritmo:

1. Comece com o vértice inicial escolhido e marque-o como visitado.
2. Explore o primeiro vértice vizinho não visitado.
3. Repita os passos 1 e 2 para este vértice vizinho.
4. Se todos os vizinhos do vértice atual foram visitados, volte (backtrack) para o vértice anterior e continue o processo.
5. O processo se repete até que todos os vértices alcançáveis a partir do vértice inicial sejam visitados.

Visualização:

Complexidade de tempo e espaço do DFS:

Complexidade de tempo:

O(V + E), onde V é o número de vértices, E é o número de arestas.

Cada nó e cada aresta do grafo são visitados uma vez.

Complexidade de espaço:

O(V), pois é usada uma pilha de chamadas ou uma pilha explícita para armazenar vértices, assim como arrays para armazenar o estado (vértices visitados).

7.2 Implementação do DFS usando recursão

Vamos primeiro implementar o DFS usando recursão — o código será bonito e compacto.

Implementação recursiva do DFS:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Processamento do nó
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# Exemplo de uso:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Implementação do DFS usando pilha

Sem recursão, o código será um pouco mais longo, já que precisamos armazenar uma lista de vértices visitados.

Implementação iterativa do DFS (usando pilha):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Processamento do nó
        
            for neighbor in reversed(graph[vertex]):  # Ordem inversa para a ordem correta de travessia
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Exemplo de uso:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Exemplos de problemas resolvidos usando DFS

Exemplos clássicos de problemas resolvidos usando DFS:

1. Busca de caminho em labirinto:

Usado para encontrar um caminho em um labirinto do ponto de início ao ponto final.

Aplicação:

Em jogos de vídeo e robótica para navegação em labirintos e espaços complexos.

2. Verificação de conectividade de grafo:

Verificação se o grafo é conectado (existe caminho entre quaisquer dois vértices).

Aplicação:

Na análise de redes para verificar a conectividade da rede.

3. Ordenação topológica:

Usado para ordenar vértices de um grafo acíclico direcionado (DAG) de forma que para qualquer aresta (u, v) o vértice u preceda o vértice v.

Aplicação:

Em compiladores para organizar dependências e tarefas.

4. Detecção de ciclos em grafo:

Verifique se o grafo contém ciclos.

Aplicação:

Na análise de dependências para detectar dependências cíclicas.

5. Geração de labirintos:

Usar DFS para gerar labirintos aleatórios.

Aplicação:

Em jogos e aplicativos de entretenimento para criar labirintos.