Exercício 22.2-4 de CLRS3 ou CLRS2 - Qual é o tempo de execução de BFS se representarmos o seu grafo de entrada por uma matriz de adjacências e modificarmos o algoritmo para tratar essa forma de entrada?
Passo 1
O enunciado pergunta qual é o tempo de execução do algoritmo BFS quando a entrada é um grafo representado por uma matriz de adjacência e o algoritmo é adaptado para essa forma de entrada. Informações relevantes que o enunciado dá ou que assumimos explicitamente:
- O grafo é
. - Denotamos
o número de vértices e o número de arestas. - A representação usada é a matriz de adjacência
de dimensão . Cada entrada indica se existe (por exemplo, ) ou não existe (por exemplo, ) uma aresta entre e . - Acessar uma entrada
da matriz tem custo constante . - O algoritmo BFS tradicional faz, para cada vértice removido da fila, um loop sobre seus vizinhos; no caso da matriz, esse “loop sobre os vizinhos” deve ser implementado varrendo todas as colunas da linha correspondente na matriz e testando
para cada . - O objetivo é expressar o tempo de execução em função de
(e possivelmente de ), e dar a resposta assintótica correta.
Passo 2
Relembrando (de forma prática) o núcleo do BFS e onde o custo aparece. O BFS faz duas coisas principais que geram custo:
- Inicialização das estruturas (cores/distâncias/antecessores) para todos os vértices.
- Loop principal: enquanto a fila não estiver vazia, retirar um vértice
e visitar todos os seus vizinhos, possivelmente enfileirando alguns vértices.
Na versão com lista de adjacência, o custo de “visitar todos os vizinhos” de todos os vértices ao longo da execução soma
no total, porque cada aresta é examinada uma vez (direcionado) durante esses loops. Por isso a versão com listas tem tempo
. Aqui, no entanto, com matriz de adjacência, o passo "para cada vizinho
de
" é substituído por “para cada
em
faça se
então …”, isto é, percorremos todas as
colunas da linha
da matriz, mesmo quando a maioria delas não corresponde a arestas.
Passo 3
Contagem detalhada das operações na versão com matriz de adjacência.
- Inicialização: para cada vértice fazemos atribuições de cor/distância/antecessor. São
vértices, logo custo . - Número de vezes que retiramos um vértice da fila: cada vértice é enfileirado/removido no máximo uma vez, então são no máximo
remoções. Para cada remoção de um vértice fazemos um loop que vai checar todas as entradas para variando sobre todo . Esse loop tem exatamente iterações (uma por coluna da matriz). - Cada iteração desse loop faz um teste de tipo “if
então …”, e o teste e acesso custam . Se houver aresta, executamos um pequeno número constante de operações adicionais (mudar cor, definir distância, enfileirar). Portanto, para cada remoção de gastamos tempo. - Como removemos até
vértices, o tempo total gasto nesses loops é . - Somando a inicialização
e as operações de fila (enfileirar/desenfileirar, também no total), o termo dominante é . - Se quisermos detalhar incluindo
: as operações feitas somente quando existe uma aresta somam , mas já contamos checagens. Logo o tempo total pode ser escrito como . Como , isso é simplesmente . Mais precisamente, o tempo é porque para grafos densos (quando é ) o custo é , e para grafos esparsos as checagens continuam obrigatórias.
Passo 4
Intuição e comparação prática (para você lembrar na prova).
- A razão prática é: com lista de adjacência você só percorre as arestas que realmente existem; com matriz, você varre todas as possíveis arestas entre pares de vértices, testando se cada uma existe. Esse teste para cada par custa tempo, daí o
. - Em termos de notação normalmente usada em algoritmos: com lista de adjacência BFS é
; com matriz de adjacência a mesma análise gera (pois e ). - Conclusão prática que vale na prova: se o grafo for denso (muito próximo de
arestas) não há perda assintótica em usar matriz; se for esparso, a matriz torna o BFS muito mais caro.
Passo 5
Exemplo numérico rápido para fixar.
- Suponha
. A matriz tem entradas. Durante o BFS, cada vez que removemos um vértice vamos checar 4 entradas dessa linha; retirando até 4 vértices fazemos até checagens — exatamente o número de entradas da matriz. Para geral fazeremos até checagens, razão do .