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 é G=(V,E).
  • Denotamos n = |V| o número de vértices e m = |E| o número de arestas.
  • A representação usada é a matriz de adjacência A de dimensão n\times n. Cada entrada A[u][v] indica se existe (por exemplo, 1) ou não existe (por exemplo, 0) uma aresta entre u e v.
  • Acessar uma entrada A[u][v] da matriz tem custo constante O(1).
  • 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 A[u][v] para cada v.
  • O objetivo é expressar o tempo de execução em função de n (e possivelmente de m), 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:
  1. Inicialização das estruturas (cores/distâncias/antecessores) para todos os vértices.
  2. Loop principal: enquanto a fila não estiver vazia, retirar um vértice u 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 O(m) no total, porque cada aresta é examinada uma vez (direcionado) durante esses loops. Por isso a versão com listas tem tempo \Theta(n+m). Aqui, no entanto, com matriz de adjacência, o passo "para cada vizinho v de u" é substituído por “para cada v em V faça se A[u][v] então …”, isto é, percorremos todas as n colunas da linha u 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 n vértices, logo custo O(n).
  • 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 n remoções. Para cada remoção de um vértice u fazemos um loop que vai checar todas as entradas A[u][v] para v variando sobre todo V. Esse loop tem exatamente n iterações (uma por coluna da matriz).
  • Cada iteração desse loop faz um teste de tipo “if A[u][v] então …”, e o teste e acesso A[u][v] custam O(1). 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 u gastamos O(n) tempo.
  • Como removemos até n vértices, o tempo total gasto nesses loops é n \times O(n) = O(n^2).
  • Somando a inicialização O(n) e as operações de fila (enfileirar/desenfileirar, também O(n) no total), o termo dominante é O(n^2).
  • Se quisermos detalhar incluindo m: as operações feitas somente quando existe uma aresta somam O(m), mas já contamos n^2 checagens. Logo o tempo total pode ser escrito como O(n^2 + m). Como m \le n^2, isso é simplesmente O(n^2). Mais precisamente, o tempo é \Theta(n^2) porque para grafos densos (quando m é \Theta(n^2)) o custo é \Theta(n^2), e para grafos esparsos as n^2 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 n^2.
  • Em termos de notação normalmente usada em algoritmos: com lista de adjacência BFS é \Theta(|V|+|E|); com matriz de adjacência a mesma análise gera \Theta(|V|^2) (pois |V|=n e |V|^2=n^2).
  • Conclusão prática que vale na prova: se o grafo for denso (muito próximo de n^2 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 n=4. A matriz tem 4\times4=16 entradas. Durante o BFS, cada vez que removemos um vértice u vamos checar 4 entradas dessa linha; retirando até 4 vértices fazemos até 4\times4=16 checagens — exatamente o número de entradas da matriz. Para n geral fazeremos até n^2 checagens, razão do \Theta(n^2).

Resposta

\Theta(|V|^2)

Exercícios relacionados