Representação computacional de Grafos

Question 1

Matriz de incidência

Answer 1

Utiliza-se uma matriz bidimensional, mas com tamanho V x E, onde V é o número de vértices e E é o número de arestas do grafo. Cada coluna da matriz representa uma aresta e cada linha representa um vértice. Os elementos da matriz indicam a relação entre os vértices e as arestas. Normalmente, valores inteiros são usados para representar a incidência, como +1 para indicar a aresta saindo de um vértice, -1 para indicar a aresta chegando em um vértice e 0 para indicar que o vértice não está relacionado à aresta. A matriz de incidência é útil para grafos direcionados e grafos com múltiplas arestas entre os mesmos vértices. Ela ocupa mais memória que a matriz de adjacência, mas menos memória que a lista de adjacência, especialmente para grafos esparsos.

Question 2

Matriz de Adjacência

Answer 2

Utiliza-se uma matriz bidimensional para representar o grafo. A matriz tem tamanho V x V, onde V é o número de vértices do grafo. Cada elemento da matriz representa uma aresta e contém um valor indicando se há uma aresta entre dois vértices. Geralmente, valores booleanos (0 ou 1) são usados para representar a presença ou ausência de uma aresta. Para grafos ponderados, os valores na matriz podem ser os pesos das arestas. A matriz de adjacência é eficiente para determinar a existência de uma aresta entre dois vértices, mas requer uma quantidade de memória proporcional ao quadrado do número de vértices.

Question 3

Lista de Adjacência

Answer 3

Utiliza-se uma estrutura de dados que armazena, para cada vértice, uma lista de seus vértices adjacentes. Isso pode ser feito usando uma matriz de listas, uma lista de listas ou uma estrutura de dados mais avançada, como uma tabela de dispersão. Cada vértice é representado por um nó que contém seu valor e uma referência para a lista de seus vizinhos. A lista de adjacência consome uma quantidade de memória proporcional ao número total de vértices e arestas do grafo, sendo mais eficiente em termos de espaço para grafos esparsos. Além disso, essa implementação permite uma busca rápida pelos vizinhos de um vértice e é útil para grafos com informações adicionais associadas a cada aresta ou vértice.

Question 4

Quando usar cada uma?

Answer 4

a matriz de incidência é uma representação que inclui vértice e aresta, a matriz de adjacência é a forma preferida de representar grafos densos, visto que indica rapidamente se existe uma aresta conectando dois vértices, e a lista de adjacência é a representação normalmente preferida para representar grafos esparsos.