Tipos de gráficos em estrutura de dados com exemplos
Sarah Chen
⚡ Resumo Inteligente
Em estruturas de dados, os grafos são coleções não lineares de vértices e arestas, classificados em famílias como grafos direcionados, não direcionados, ponderados, cíclicos, acíclicos, completos, conexos, bipartidos, de Euler e de Hamilton, com base em sua estrutura.
Um grafo é 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 uma ligação entre um par de vértices.
Os grafos podem ser de vários tipos, dependendo da posição dos nós e arestas. Aqui estão alguns tipos importantes de grafos:
Gráfico direcionado
As arestas de um grafo direcionado contêm setas que indicam a direção. A seta determina para onde a aresta aponta ou onde ela termina. Aqui está um exemplo de um grafo direcionado.
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
Um grafo não direcionado contém arestas sem ponteiros. Isso significa que podemos percorrer o caminho inverso entre dois vértices. Aqui está um exemplo simples de um grafo não direcionado.
Gráfico não direcionado
No gráfico acima,
- Podemos ir de A para B.
- Também podemos ir de B para A.
- As arestas não contêm direções.
É um exemplo de um grafo não direcionado que possui um número finito de vértices e arestas, sem pesos.
Gráfico ponderado
Um grafo que contém pesos ou custos nas arestas é chamado de grafo ponderado. O valor numérico geralmente representa o custo de movimentação de um vértice para outro. Tanto grafos direcionados quanto não direcionados podem ter pesos em suas arestas. Aqui está um exemplo de um grafo ponderado (direcionado).
Gráfico direcionado com peso
- De A para B, existe uma aresta, e o peso é 5, o que significa que mover-se de A para B nos custará 5.
- A aponta para B, mas neste grafo, B não tem aresta direta sobre A. Portanto, não podemos ir de B para A.
- No entanto, se quisermos ir de A para F, existem vários caminhos. Os caminhos são ADF e 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 um grafo não direcionado com pesos:
Gráfico não direcionado com peso
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
Os grafos bidirecionais e não direcionados têm uma propriedade em comum. Ou seja:
- Em geral, um grafo 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:
Gráfico bidirecional
Viajar de A para D custará 17, mas viajar de D para A custará 12. Portanto, não podemos atribuir dois pesos diferentes se for um grafo não direcionado.
Gráfico Infinito
O grafo conterá um número infinito de arestas e nós. Se um grafo é infinito e também conexo, então ele 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 outras arestas. Aqui está um exemplo de um grafo infinito:
Gráfico Infinito
Gráfico Nulo
Um grafo nulo contém apenas nós ou vértices, mas nenhuma aresta. Dado um grafo G = (V, E), onde V representa os vértices e E as arestas, ele será nulo se o número de arestas E for zero. Aqui está um exemplo de um grafo nulo:
Gráfico Nulo
Gráfico Trivial
Uma estrutura de dados em forma de grafo é considerada trivial se possuir apenas um vértice ou nó, sem arestas. Aqui está um exemplo de um grafo trivial:
Multigráfico
Um grafo é chamado de multigrafo quando existem múltiplas arestas entre dois vértices, ou quando um vértice possui um laço. O termo "laço" em Estrutura de Dados de Grafos significa uma aresta que aponta para o mesmo nó ou vértice. Um multigrafo pode ser direcionado ou não direcionado. Aqui está um exemplo de um multigrafo:
Existem duas arestas de B para A. Além disso, o vértice E possui um laço. O grafo acima é um grafo direcionado sem pesos nas arestas.
Gráfico Completo
Um grafo é completo se cada vértice possui arestas direcionadas ou não direcionadas que o conectam a todos os outros vértices. Suponha que haja um total de V vértices e que cada vértice possua exatamente V-1 arestas. Então, esse grafo será chamado de grafo completo. Nesse tipo de grafo, cada vértice está conectado a todos os outros vértices por meio de arestas. Aqui está um exemplo de um grafo completo com cinco vértices:
Como você pode ver na imagem, o número total de nós é cinco e todos os nós têm exatamente quatro arestas.
Gráfico Conectado
Um grafo é chamado de grafo conexo se, partindo de um nó ou vértice, for possível percorrer todos os outros nós a partir desse nó inicial. Para isso, deve haver pelo menos uma aresta entre cada par de nós ou vértices. Aqui está um exemplo de um grafo conexo:
Segue abaixo uma explicação do grafo conectado acima:
- Supondo que não haja aresta entre C e F, não podemos viajar de A para G. No entanto, a aresta de C para F nos permite viajar para qualquer nó a partir de um nó dado.
- 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 grafo é dito cíclico se apresentar um ou mais ciclos. Aqui está um exemplo de um grafo cíclico:
Aqui, os vértices A, B e C formam um ciclo. Um grafo pode conter múltiplos ciclos.
Gráfico Acíclico Direcionado (DAG)
Um grafo é chamado de Grafo Acíclico Direcionado ou DAG se não houver ciclos dentro do grafo. O DAG é importante ao realizar... Classificação Topológica ou para encontrar a ordem de execução. O DAG também é importante para criar sistemas de agendamento ou analisar a dependência de recursos, etc. No entanto, o grafo acima não contém nenhum ciclo. Aqui está um exemplo simples de um Grafo Acíclico Direcionado (DAG):
Gráfico de Ciclo
Um grafo ciclo não é o mesmo que um grafo cíclico. Em um grafo ciclo, cada nó terá exatamente duas arestas conectadas, o que significa que cada nó terá exatamente dois graus. Aqui está um exemplo de um grafo ciclo:
Gráfico Bipartido
Esses tipos de Gráficos São tipos especiais de grafos onde os vértices são atribuídos a dois conjuntos. Um grafo bipartido deve seguir a regra:
- Os dois conjuntos de vértices devem ser distintos, o que significa que todos os vértices devem ser divididos em dois grupos ou conjuntos.
- Vértices do mesmo conjunto não devem formar arestas.
Gráfico de Euler
Uma estrutura de dados do tipo grafo é considerada um grafo euleriano se todos os seus vértices tiverem grau par. O termo grau de um vértice significa o número de arestas que apontam para um determinado vértice ou que partem dele. Aqui está um exemplo de um grafo euleriano:
Todos os vértices têm graus pares. Os vértices A, D, E e H têm graus dois. Aqui, o nó C tem graus quatro, que é par.
Gráfico de Hamilton
Um grafo hamiltoniano é um grafo conexo, onde você pode visitar todos os vértices a partir de um vértice dado sem revisitar o mesmo nó ou usar a mesma aresta. Esse tipo de grafo conexo é conhecido como "grafo hamiltoniano". O caminho percorrido para verificar se um determinado grafo é um grafo hamiltoniano ou não é conhecido como caminho hamiltoniano. Aqui está um exemplo simples de um grafo hamiltoniano:
Nesta imagem, podemos visitar todos os vértices de qualquer nó do gráfico acima. Um dos caminhos pode ser ADCHBETambém é possível encontrar um Ciclo Hamiltoniano. Um Ciclo Hamiltoniano começa e termina no mesmo vértice. Portanto, o Ciclo Hamiltoniano será ADCHBEA.
