Matriz de adjacência

---

A ideia por trás da matriz de adjacência é usar uma matriz (uma tabela ou grade) quadrada, onde o número de linhas e colunas é igual ao número de vértices do grafo.

Definição

Para um grafo $G=(V,E)$, a matriz de adjacência $A$ de dimensão $|V|\times |V|$ é definida da seguinte forma:

• O elemento $a_{ij}$ da matriz é $1$ se existe uma aresta conectando o vértice $i$ e o vértice $j$.
• O elemento $a_{ij}$ é $0$ se não existe uma aresta entre eles.

Exemplo

Para o grafo de 5 vértices, é criada uma matriz $5\times 5$.

NOTE

Uma característica importante para Grafos não direcionados é que a matriz é simétrica, ou seja, ela é igual a sua transposta.

Análise

Vantagem: É muito rápido verificar se dois vértices são vizinhos. A busca leva tempo constante $O(1)$ pois a estrutura de vetor garante essa eficiente no acesso de qualquer elemento pelo seus índices.

Desvantagem: o uso de memória é de $O(|V{|}^2)$, o que pode ser muito ineficiente para grafos com muitos vértices e poucas arestas (grafos esparsos).

Referências

---

Teoria dos grafos - Representação de grafos