Time and Space Complexity
Lição 7 de 9 do curso Busca em Profundidade - Algoritmos de Grafos da Coddy.
Complexidade de Tempo:
- O(V + E)
- A construção da lista de adjacência percorre cada aresta uma vez, e a travessia visita cada vértice e analisa cada aresta um número constante de vezes.
Complexidade de Espaço:
- O(V + E)
- A lista de adjacência armazena cada aresta, e o array visitado e a pilha comportam, cada um, até V vértices.
Resumo:
- O DFS explora profundamente primeiro, retrocedendo (backtracking) quando não há mais vizinhos não visitados.
- Ele é executado em tempo linear e é a base de muitos algoritmos de grafos.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Busca em Profundidade - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity