Tipos de gráficos em estrutura de dados com exemplos

Um gráfico é uma estrutura de dados não linear que consiste em vértices e arestas. Os vértices contêm as informações ou dados, e as arestas funcionam como um link entre pares de vértices.

Os gráficos podem ser de vários tipos, dependendo da posição dos nós e arestas. Aqui estão alguns tipos importantes de gráficos:

Gráfico direcionado

As bordas do gráfico direcionado contêm setas que indicam a direção. A seta determina para onde a borda aponta ou termina.

Aqui está um exemplo do gráfico direcionado.

Podemos ir do nó A ao D.
No entanto, não podemos ir do nó D para o nó A, pois a aresta aponta de A para D.
Como o gráfico não possui pesos, viajar do vértice A ao D custará o mesmo que viajar de D ao F.

Gráfico não direcionado

O gráfico não direcionado contém arestas sem ponteiros. Isso significa que podemos viajar vice-versa entre dois vértices.

Aqui está um exemplo simples de gráfico não direcionado.

No gráfico acima,

Podemos passar de A para B
Também podemos passar de B para A
As arestas não contêm direções.

É um exemplo de gráfico não direcionado com um número finito de vértices e arestas sem pesos.

Gráfico ponderado

O gráfico que contém pesos ou custos nas arestas é chamado de gráfico ponderado. O valor numérico geralmente representa o custo de movimentação de um vértice para outro. Tanto o gráfico direcionado quanto o não direcionado podem ter pesos em suas bordas.

Aqui está um exemplo de gráfico ponderado (Direcionado).

De A para B, há uma aresta e o peso é 5, o que significa que passar de A para B nos custará 5.
Um ponto para B, mas neste gráfico, B não tem aresta direta sobre A. Portanto, não podemos viajar de B para A.
No entanto, se quisermos passar de A para F, existem vários caminhos. Os caminhos são ADF, ABF. ADF custará (10+11) ou 21.
Aqui, o caminho ABF custará (5+15) ou 20. Aqui estamos adicionando o peso de cada aresta no caminho.

Aqui está um exemplo de gráfico não direcionado com pesos:

Aqui, a borda tem peso, mas não tem direção. Então, significa que viajar do vértice A ao D custará 10 e vice-versa.

Gráfico bidirecional

Gráficos bidirecionais e não direcionados têm uma propriedade comum. Aquilo é

Geralmente, o gráfico não direcionado pode ter uma aresta entre dois vértices.

Por exemplo:

Aqui, passar de A para D ou de D para A custará 10.
Em um gráfico bidirecional, podemos ter duas arestas entre dois vértices.

Aqui está um exemplo:

Viajar de A para D nos custará 17, mas viajar de D para A nos custará 12. Portanto, não podemos atribuir dois pesos diferentes se for um gráfico não direcionado.

Gráfico Infinito

O gráfico conterá um número infinito de arestas e nós. Se um gráfico for infinito e também for um gráfico conectado, ele também conterá um número infinito de arestas. Aqui, as arestas estendidas significam que mais arestas podem ser conectadas a esses nós por meio de arestas.

Aqui está um exemplo do gráfico infinito:

Gráfico Nulo

O gráfico nulo contém apenas nós ou vértices, mas sem arestas. Se for dado um gráfico G = (V, E), onde V são vértices e E são arestas, será nulo se o número de arestas E for zero.

Aqui está um exemplo de gráfico nulo:

Gráfico Trivial

Uma estrutura de dados de gráfico é considerada trivial se apenas um vértice ou nó estiver presente sem arestas.

Aqui está um exemplo de gráfico trivial:

Multigráfico

Um gráfico é chamado de multigrafo quando múltiplas arestas estão presentes entre dois vértices ou o vértice possui um loop. O termo “Loop” na estrutura de dados do gráfico significa uma aresta apontando para o mesmo nó ou vértice. O multigrafo pode ser direcionado ou não direcionado.

Aqui está um exemplo de multigráfico:

Existem duas arestas de B a A. Além disso, o vértice E possui um auto-loop. O gráfico acima é um gráfico direcionado sem pesos nas arestas.

Gráfico Completo

Um gráfico está completo se cada vértice tiver arestas direcionadas ou não direcionadas com todos os outros vértices.

Suponha que haja um número total V de vértices e cada vértice tenha exatamente V-1 arestas. Então, este gráfico será chamado de gráfico completo. Neste tipo de gráfico, cada vértice está conectado a todos os outros vértices por meio de arestas.

Aqui está um exemplo de gráfico completo com cinco vértices:

Você pode ver na imagem que o número total de nós é cinco e todos os nós têm exatamente quatro arestas.

Gráfico Conectado

Um gráfico é chamado de gráfico conectado se começarmos a partir de um nó ou vértice e percorrermos todos os nós a partir do nó inicial. Para isso, deve haver pelo menos uma aresta entre cada par de nós ou vértices.

Aqui está um exemplo de gráfico conectado:

Aqui estão algumas explicações do gráfico de “exemplo de gráfico completo” acima:

Supondo que não haja aresta entre C e F, não podemos viajar de A para G. No entanto, a aresta C para F nos permite viajar para qualquer nó a partir de um determinado nó.
Um gráfico completo é um gráfico conectado porque podemos passar de um nó para qualquer outro nó no gráfico fornecido.

Gráfico Cíclico

Um gráfico é considerado cíclico se houver um ou mais ciclos presentes no gráfico.

Aqui está um exemplo de gráfico cíclico:

Aqui, os vértices A, B e C formam um ciclo.

Um gráfico pode ter vários ciclos dentro dele.

Gráfico Acíclico Direcionado (DAG)

Um gráfico é chamado de gráfico acíclico direcionado ou DAG se não houver ciclos dentro de um gráfico. DAG é importante ao fazer o Classificação Topológica ou encontrar a ordem de execução. O DAG também é importante para criar sistemas de agendamento ou verificar dependências de recursos, etc. No entanto, o gráfico acima não contém nenhum ciclo interno.

Aqui está um exemplo simples de gráfico acíclico direcionado (DAG):

Gráfico de Ciclo

O gráfico de ciclo não é igual ao gráfico cíclico. No Cycle Graph, cada nó terá exatamente duas arestas conectadas, o que significa que cada nó terá exatamente dois graus.

Aqui está um exemplo de gráfico de ciclo:

Gráfico Bipartido

Esses tipos de Gráficos são tipos especiais de gráfico onde os vértices são atribuídos a dois conjuntos.

O Gráfico Bipartido deve seguir a regra:

Dois conjuntos de vértices devem ser distintos, o que significa que todos os vértices devem ser divididos em dois grupos ou conjuntos.
O mesmo conjunto de vértices não deve formar arestas.

Gráfico de Euler

As estruturas de dados do gráfico são consideradas um gráfico de Euler se todos os vértices tiverem um grau par. O termo grau de vértices significa o número de arestas apontando ou apontando para um determinado vértice.

Aqui está um exemplo de gráfico de Euler:

Todos os vértices têm graus pares. Os vértices A, D, E e H têm dois graus. Aqui, o nó C tem quatro graus, o que é par.

Gráfico de Hamilton

Hamilton Graph é um Connect Graph, onde você pode visitar todos os vértices de um determinado vértice sem revisitar o mesmo nó ou usar a mesma aresta. Este tipo de gráfico conectado é conhecido como “Gráfico de Hamilton”. O caminho que você visita para verificar se o gráfico fornecido é um gráfico de Hamilton ou não é conhecido como caminho hamiltoniano.

Aqui está um exemplo gráfico simples de um Hamilton:

Nesta imagem, podemos visitar todos os vértices de qualquer nó do gráfico acima. Um dos caminhos pode ser ADCHBE. Também é possível encontrar um Ciclo de Hamilton. O Ciclo de Hamilton começa e termina no mesmo vértice. Portanto, o Ciclo de Hamilton será ADCHBEA.