Time and Space Complexity
Lição 7 de 9 do curso Busca em Largura (BFS) - Algoritmos de Grafos da Coddy.
Complexidade de Tempo:
- O(V + E)
- Cada vértice é enfileirado e desenfileirado uma vez, e cada aresta é examinada um número constante de vezes.
Complexidade de Espaço:
- O(V + E)
- A lista de adjacência armazena cada aresta, e a fila e o array visitado contêm até V vértices.
Resumo:
- O BFS explora em camadas usando uma fila, visitando vértices mais próximos antes dos mais distantes.
- Essa ordem em camadas o torna o algoritmo padrão para caminhos mais curtos em grafos não ponderados.
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 Largura (BFS) - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity