1. Por que, em uma matriz de adjacências, verificar a existência de uma aresta é O(1).

Passo 1

O enunciado pergunta por que, usando uma matriz de adjacências para representar um grafo, a verificação da existência de uma aresta entre dois vértices é feita em tempo constante.

Passo 2

Precisamos lembrar que uma matriz de adjacências é basicamente uma matriz bidimensional A de tamanho n times n, onde n é o número de vértices do grafo, e cada entrada A[i][j] indica se há (ou não) uma aresta entre o vértice i e o vértice j.
Para verificar se existe uma aresta entre os vértices u e v, basta acessar diretamente o elemento A[u][v]. Não precisamos percorrer nenhuma estrutura nem fazer algum cálculo adicional: fazemos um único acesso à matriz.

Passo 3

Em termos de estruturas de dados, acessar um elemento de um array (ou de um arranjo bidimensional) por índice é uma operação de tempo constante, ou seja, O(1).
Portanto, na representação por matriz, a consulta A[u][v] não depende de n nem de outra variável: é sempre uma única operação de leitura.

Resposta

Porque basta um único acesso direto ao elemento da matriz de adjacências ( A[u][v]), e esse acesso a um array por índice é uma operação de tempo constante, ou seja, O(1).

Exercícios relacionados