Neste tutorial, você aprenderá o que é uma estrutura de dados de gráfico. Além disso, você encontrará representações de um gráfico.
Uma estrutura de dados de gráfico é uma coleção de nós que possuem dados e estão conectados a outros nós.
Vamos tentar entender isso por meio de um exemplo. No facebook, tudo é um nó. Isso inclui usuário, foto, álbum, evento, grupo, página, comentário, história, vídeo, link, nota … qualquer coisa que tenha dados é um nó.
Todo relacionamento é uma borda de um nó a outro. Quer você poste uma foto, participe de um grupo, como uma página, etc., uma nova vantagem é criada para esse relacionamento.
Exemplo de estrutura de dados de gráfico
Todo o Facebook é então uma coleção desses nós e arestas. Isso ocorre porque o Facebook usa uma estrutura de dados de gráfico para armazenar seus dados.
Mais precisamente, um gráfico é uma estrutura de dados (V, E) que consiste em
- Uma coleção de vértices V
- Uma coleção de arestas E, representadas como pares ordenados de vértices (u, v)
Vértices e arestas
No gráfico,
V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)
Terminologia de gráfico
- Adjacência : Diz-se que um vértice está adjacente a outro vértice se houver uma aresta conectando-os. Os vértices 2 e 3 não são adjacentes porque não há aresta entre eles.
- Caminho : uma sequência de arestas que permite ir do vértice A ao vértice B é chamada de caminho. 0-1, 1-2 e 0-2 são caminhos do vértice 0 ao vértice 2.
- Gráfico direcionado : um gráfico no qual uma aresta (u, v) não significa necessariamente que também haja uma aresta (v, u). As arestas em tal gráfico são representadas por setas para mostrar a direção da aresta.
Representação gráfica
Os gráficos são comumente representados de duas maneiras:
1. Matriz de Adjacência
Uma matriz de adjacência é um array 2D de vértices V x V. Cada linha e coluna representam um vértice.
Se o valor de qualquer elemento a(i)(j)for 1, ele representa que há uma aresta conectando o vértice i e o vértice j.
A matriz de adjacência para o grafo que criamos acima é
Matriz de adjacência de grafos
Por ser um gráfico não direcionado, para a aresta (0,2), também precisamos marcar a aresta (2,0); tornando a matriz de adjacência simétrica em relação à diagonal.
A pesquisa de aresta (verificando se existe uma aresta entre o vértice A e o vértice B) é extremamente rápida na representação da matriz de adjacência, mas temos que reservar espaço para cada ligação possível entre todos os vértices (V x V), portanto, requer mais espaço.
2. Lista de Adjacência
Uma lista de adjacência representa um gráfico como uma matriz de listas vinculadas.
O índice da matriz representa um vértice e cada elemento em sua lista vinculada representa os outros vértices que formam uma aresta com o vértice.
A lista de adjacências para o grafo que fizemos no primeiro exemplo é a seguinte:
Representação de lista de adjacência
Uma lista de adjacências é eficiente em termos de armazenamento, pois só precisamos armazenar os valores das arestas. Para um gráfico com milhões de vértices, isso pode significar muito espaço economizado.
Operações de gráfico
As operações de gráfico mais comuns são:
- Verifique se o elemento está presente no gráfico
- Gráfico Traversal
- Adicione elementos (vértice, arestas) ao gráfico
- Encontrando o caminho de um vértice para outro
