- Por que, em uma matriz de adjacências, verificar a existência de uma aresta é
.
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
de tamanho
, onde
é o número de vértices do grafo, e cada entrada
indica se há (ou não) uma aresta entre o vértice
e o vértice
.
Para verificar se existe uma aresta entre os vértices e
, basta acessar diretamente o elemento
. Não precisamos percorrer nenhuma estrutura nem fazer algum cálculo adicional: fazemos um único acesso à matriz.
Para verificar se existe uma aresta entre os vértices
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,
.
Portanto, na representação por matriz, a consulta não depende de
nem de outra variável: é sempre uma única operação de leitura.
Portanto, na representação por matriz, a consulta
Resposta
Porque basta um único acesso direto ao elemento da matriz de adjacências (
), e esse acesso a um array por índice é uma operação de tempo constante, ou seja,
.