Estrutura de dados - Estrutura de dados do gráfico

Um gráfico é uma representação pictórica de um conjunto de objetos onde alguns pares de objetos são conectados por links. Os objetos interconectados são representados por pontos denominados comovertices, e os links que conectam os vértices são chamados edges.

Formalmente, um gráfico é um par de conjuntos (V, E), Onde V é o conjunto de vértices e Eé o conjunto de arestas, conectando os pares de vértices. Dê uma olhada no gráfico a seguir -

No gráfico acima,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Estrutura de dados do gráfico

Os gráficos matemáticos podem ser representados na estrutura de dados. Podemos representar um gráfico usando uma matriz de vértices e uma matriz bidimensional de arestas. Antes de prosseguirmos, vamos nos familiarizar com alguns termos importantes -

• Vertex- Cada nó do gráfico é representado como um vértice. No exemplo a seguir, o círculo rotulado representa vértices. Assim, A a G são vértices. Podemos representá-los usando um array, conforme mostrado na imagem a seguir. Aqui, A pode ser identificado pelo índice 0. B pode ser identificado usando o índice 1 e assim por diante.

• Edge- Edge representa um caminho entre dois vértices ou uma linha entre dois vértices. No exemplo a seguir, as linhas de A a B, B a C e assim por diante representam as arestas. Podemos usar uma matriz bidimensional para representar uma matriz, conforme mostrado na imagem a seguir. Aqui AB pode ser representado como 1 na linha 0, coluna 1, BC como 1 na linha 1, coluna 2 e assim por diante, mantendo as outras combinações como 0.

• Adjacency- Dois nós ou vértices são adjacentes se estiverem conectados um ao outro por meio de uma aresta. No exemplo a seguir, B é adjacente a A, C é adjacente a B e assim por diante.

• Path- O caminho representa uma sequência de arestas entre os dois vértices. No exemplo a seguir, ABCD representa um caminho de A a D.

Operações básicas

A seguir estão as operações básicas básicas de um gráfico -

• Add Vertex - Adiciona um vértice ao gráfico.

• Add Edge - Adiciona uma aresta entre os dois vértices do gráfico.

• Display Vertex - Exibe um vértice do gráfico.

Para saber mais sobre o Graph, leia o Tutorial da teoria do Graph . Aprenderemos como percorrer um gráfico nos próximos capítulos.