Lista de Adjacências e Representação Matricial do Gráfico

Embora pareçam diferentes, todos tipos de gráficos pode ser representado de maneira semelhante. Geralmente existem dois tipos de representação gráfica:

  1. Matriz de adjacência
  2. Lista de Adjacência

Lista de Adjacência

A Lista de Adjacência consiste em Listas Vinculadas. Cada vértice é considerado um índice de array e cada elemento representa uma lista vinculada. Essas listas vinculadas contêm os vértices que possuem arestas com o vértice do índice.

Aqui está um exemplo de lista de adjacências:

Lista de Adjacência

Digamos que um gráfico contenha um número V de vértices e um número E de arestas.

Geralmente, o espaço complexserá O(V + E).

Pior caso espaço complexserá O(V2) se o gráfico fornecido for o gráfico completo

Matriz de adjacência

Matriz de Adjacência é composta por uma matriz 2D. Gráfico tendo um número V de vértices, o tamanho da matriz será VxV.

Dizer, matrix[i][j] = 5. Isso significa que há uma aresta entre os nós i e j onde o peso é 5.

Vejamos o seguintewing Gráfico e sua matriz de adjacência:

Matriz de adjacência

Nós criamos o Matriz 2D usando estas etapas:

Passo 1) O vértice A tem uma aresta direta com B e o peso é 5. Portanto, a célula da linha A e da coluna B será preenchida com 5. O restante das células da linha A será preenchido com zero.

Passo 2) Os vértices B têm uma aresta direta com C e o peso é 4. Portanto, a célula na linha B e na coluna C será preenchida com 4. As células restantes na linha B serão preenchidas com zero, pois B não tem aresta de saída para qualquer outros nós.

Passo 3) Os vértices C não possuem arestas diretas com nenhum outro vértice. Portanto, a linha C será preenchida com zeros.

Passo 4) O vértice D tem uma aresta direcionada com A e C.

  • Aqui, a célula na linha D e na coluna A terá o valor 7. As células na linha D e na coluna C terão o valor 2.
  • O restante das células da linha D será preenchida com zeros.

Passo 5) Os vértices E têm uma aresta direcionada com B e D. A célula na linha E e na coluna B terá um valor de 6. As células na linha E e na coluna D terão um valor de 3. O restante das células na linha D será preenchido com zeros.

Aqui estão alguns pontos a serem observados:

  • O gráfico não possui loops próprios quando a diagonal primária da matriz de adjacência é 0.
  • The Graph is a directed graph if the indexes (a,b) and (b,a) don’t have the same value. Otherwise, the Graph is a directed graph.
  • O gráfico será um gráfico ponderado se o valor das células for maior que 1.

Há algum problema com a matriz de adjacência, pois requer espaços quadrados. Aqui, estamos armazenando as arestas que não estão conectadas. Essas arestas alocam espaço na memória.

Por exemplo, se tivermos um gráfico com 100 nós, então serão necessárias 10 mil células para armazená-lo no RAM. Com menos arestas no gráfico, alocar uma memória tão grande pode ser um desperdício. Então, o espaço complexA capacidade de usar a matriz de adjacência será O(N2), onde N significa o número de nós no gráfico.