5. Complexidade
Roteiro (o que analisamos nesta parte):
- Complexidade de tempo com lista de adjacência
- Por que cada vértice é processado uma vez
- Por que cada aresta é examinada no máximo duas vezes
- Comparação com matriz de adjacência
- Complexidade de espaço
- Insight estrutural
Agora que a correção foi estabelecida, analisamos o algoritmo sob a perspectiva computacional.
5.1 Complexidade de Tempo (Lista de Adjacência)
O(|V| + |E|)
Esse limite é ótimo para a travessia de grafos.
5.2 Processamento de Vértices
- Descoberto uma vez
- Enfileirado uma vez
- Desenfileirado uma vez
- Colorido como BLACK uma vez
O(|V|)
5.3 Exame de Arestas
Cada aresta é examinada no máximo duas vezes (caso não direcionado).
O(|E|)
5.4 Caso da Matriz de Adjacência
O(|V|^2)
Para grafos esparsos, listas de adjacência são assintoticamente superiores.
5.5 Complexidade de Espaço
O(|V|)
5.6 Insight Estrutural
- Sem revisitas
- Sem exploração redundante
- Ordem estrita por camadas imposta pela fila FIFO
Próxima: Parte 6 — Árvore BFS & Reconstrução de Caminhos
Com a correção e a complexidade compreendidas, agora focamos no que o BFS realmente produz: os ponteiros de predecessores formam uma árvore BFS, e essa árvore nos permite reconstruir os menores caminhos da fonte até qualquer vértice alcançável.