Algoritmo de busca em profundidade que explora o grafo indo o mais fundo possível antes de retroceder.
DFS (Depth-First Search) explora um grafo indo o mais fundo possível em cada ramo antes de retroceder. Imagine explorar um labirinto: você segue um corredor até o fim, depois volta e tenta outro caminho. A ideia é simples: visite um vértice, marque como visitado, e recursivamente visite todos os vizinhos não visitados. Quando não houver mais vizinhos para explorar, retroceda (backtrack) para o vértice anterior. DFS pode ser implementado de duas formas: - Recursivo: usa a pilha de chamadas do sistema - Iterativo: usa uma pilha explícita A versão recursiva é mais elegante, mas pode causar stack overflow em grafos muito profundos. A versão iterativa é mais segura para grafos grandes.
“DFS usa uma pilha (implícita na recursão ou explícita) para lembrar de onde veio, permitindo explorar profundamente e depois retroceder.”
Cada vértice é visitado uma vez, e cada aresta é examinada uma vez.
O conjunto visited garante que cada vértice entra no processamento apenas uma vez. Para cada vértice, iteramos sobre suas arestas adjacentes.
No pior caso, a pilha de recursão pode ter todos os vértices (grafo linear).
Mesmo no melhor caso, precisamos verificar todas as arestas.
Visitamos todos os vértices e examinamos todas as arestas.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| DFS(atual) | O(V + E) | O(V) | Detecção de ciclos, ordenação topológica, componentes conexos |
| BFS | O(V + E) | O(V) | Caminho mais curto em grafos sem peso, níveis de distância |
| Dijkstra | O((V+E) log V) | O(V) | Caminho mais curto com pesos positivos |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def dfs_recursive(graph, start, visited=None):Definição2 if visited is None:Conjunto Visitados3 visited = set()Conjunto Visitados4 5 if start in visited:Caso Base6 returnCaso Base7 8 visited.add(start)Marcar Visitado9 print(start)Processar Vértice10 11 for neighbor in graph[start]:Recursão12 dfs_recursive(graph, neighbor, visited)Recursão13 14 15def dfs_iterative(graph, start):Definição16 visited = set()Conjunto Visitados17 stack = [start]Empilhar18 19 while stack:Loop Principal20 vertex = stack.pop()Desempilhar21 22 if vertex in visited:Caso Base23 continueCaso Base24 25 visited.add(vertex)Marcar Visitado26 print(vertex)Processar Vértice27 28 for neighbor in graph[vertex]:Recursão29 if neighbor not in visited:Recursão30 stack.append(neighbor)Empilhar31