Tipos de gráficos en estructura de datos con ejemplos

Tipos de gráficos en estructura de datos

Un gráfico es una estructura de datos no lineal que consta de vértices y aristas. Los vértices contienen la información o los datos y los bordes funcionan como un vínculo entre un par de vértices.

Los gráficos pueden ser de varios tipos, según la posición de los nodos y los bordes. Aquí hay algunos tipos importantes de gráficos:

Gráfico dirigido

Los bordes del gráfico dirigido contienen flechas que indican la dirección. La flecha determina hacia dónde apunta o termina el borde.

A continuación se muestra un ejemplo de gráfico dirigido.

Gráfico dirigido
Gráfico dirigido
  • Podemos ir del Nodo A al D.
  • Sin embargo, no podemos pasar del nodo D al nodo A ya que el borde apunta de A a D.
  • Como el Gráfico no tiene pesos, viajar del vértice A al D costará lo mismo que viajar de D a F.

Gráfico no dirigido

El gráfico no dirigido contiene aristas sin punteros. Significa que podemos viajar viceversa entre dos vértices.

A continuación se muestra un ejemplo sencillo de gráfico no dirigido.

Gráfico no dirigido
Gráfico no dirigido

En el gráfico anterior,

  • Podemos pasar de A a B
  • También podemos pasar de B a A.
  • Los bordes no contienen direcciones.

Es un ejemplo de un gráfico no dirigido que tiene un número finito de vértices y aristas sin pesos.

Gráfico ponderado

El gráfico que contiene pesos o costos en los bordes se llama gráfico ponderado. El valor numérico generalmente representa el costo de mover de un vértice a otro. Tanto el gráfico dirigido como el no dirigido pueden tener pesos en sus bordes.

A continuación se muestra un ejemplo de gráfico ponderado (dirigido).

Gráfico dirigido con peso
Gráfico dirigido con peso
  • De A a B, hay una ventaja y el peso es 5, lo que significa que pasar de A a B nos costará 5.
  • A apunta a B, pero en esta gráfica, B no tiene ventaja directa sobre A. Por lo tanto, no podemos viajar de B a A.
  • Sin embargo, si queremos pasar de A a F, existen varios caminos. Los caminos son ADF, ABF. El ADF costará (10+11) o 21.
  • Aquí, la ruta ABF costará (5+15) o 20. Aquí sumamos el peso de cada borde en la ruta.

A continuación se muestra un ejemplo de un gráfico no dirigido con ponderaciones:

Gráfico no dirigido con peso
Gráfico no dirigido con peso

Aquí, el borde tiene peso pero no dirección. Entonces, significa que viajar del vértice A al D costará 10 y viceversa.

Gráfico bidireccional

Los gráficos bidireccionales y no dirigidos tienen una propiedad común. Eso es

  • Generalmente, el gráfico no dirigido puede tener un borde entre dos vértices.

Por ejemplo:

Gráfico bidireccional

  • Aquí, pasar de A a D o de D a A costará 10.
  • En un gráfico bidireccional, podemos tener dos aristas entre dos vértices.

Aquí hay un ejemplo:

Gráfico bidireccional
Gráfico bidireccional

Viajar de A a D nos costará 17, pero viajar de D a A nos costará 12. Por lo tanto, no podemos asignar dos pesos diferentes si se trata de un grafo no dirigido.

Gráfico infinito

El gráfico contendrá un número infinito de aristas y nodos. Si un gráfico es infinito y también es un gráfico conexo, entonces también contendrá un número infinito de aristas. Aquí, los bordes extendidos significan que se pueden conectar más bordes a estos nodos a través de bordes.

Aquí hay un ejemplo del gráfico infinito:

Gráfico infinito
Gráfico infinito

Gráfico nulo

Null Graph contiene solo nodos o vértices pero sin aristas. Si se le da un gráfico G = (V, E), donde V son vértices y E son aristas, será nulo si el número de aristas E es cero.

Aquí hay un ejemplo de un gráfico nulo:

Gráfico nulo
Gráfico nulo

Gráfico trivial

Una estructura de datos de gráfico se considera trivial si solo hay un vértice o nodo sin aristas.

Aquí hay un ejemplo de un gráfico trivial:

Gráfico trivial

Gráfico múltiple

Un gráfico se llama multigrafo cuando hay múltiples aristas entre dos vértices o el vértice tiene un bucle. El término "bucle" en la estructura de datos del gráfico significa un borde que apunta al mismo nodo o vértice. Multigraph puede ser dirigido o no dirigido.

Aquí hay un ejemplo de un gráfico múltiple:

Gráfico múltiple

Hay dos aristas de B a A. Además, el vértice E tiene un bucle propio. El gráfico anterior es un gráfico dirigido sin pesos en los bordes.

Gráfico completo

Un gráfico está completo si cada vértice tiene aristas dirigidas o no dirigidas con todos los demás vértices.

Supongamos que hay un número total V de vértices y cada vértice tiene exactamente V-1 aristas. Entonces, este Gráfico se llamará Gráfico Completo. En este tipo de gráfico, cada vértice está conectado a todos los demás vértices mediante aristas.

Aquí hay un ejemplo de un gráfico completo con cinco vértices:

Gráfico completo

Puede ver en la imagen que el número total de nodos es cinco y todos los nodos tienen exactamente cuatro aristas.

Gráfico conectado

Un Gráfico se llama Gráfico Conectado si partimos de un nodo o vértice y recorremos todos los nodos desde el nodo inicial. Para ello, debe existir al menos una arista entre cada par de nodos o vértices.

Aquí hay un ejemplo de un gráfico conectado:

Gráfico conectado

Aquí hay una explicación del gráfico de “ejemplo de gráfico completo” anterior:

  • Suponiendo que no hay una arista entre C y F, no podemos viajar de A a G. Sin embargo, la arista C a F nos permite viajar a cualquier nodo desde un nodo determinado.
  • Un gráfico completo es un gráfico conectado porque podemos pasar de un nodo a cualquier otro nodo en el gráfico dado.

Gráfico cíclico

Se dice que un gráfico es cíclico si hay uno o más ciclos presentes en el gráfico.

Aquí hay un ejemplo de un gráfico cíclico:

Gráfico cíclico

Aquí, los vértices A, B y C forman un ciclo.

Un gráfico puede tener múltiples ciclos en su interior.

Gráfico acíclico dirigido (DAG)

Un gráfico se llama gráfico acíclico dirigido o DAG si no hay ciclos dentro de un gráfico. DAG es importante al hacer el Orden topológico o encontrar la orden de ejecución. DAG también es importante para crear sistemas de programación o escanear dependencias de recursos, etc. Sin embargo, el gráfico anterior no contiene ningún ciclo en su interior.

Aquí hay un ejemplo simple de un gráfico acíclico dirigido (DAG):

Gráfico acíclico dirigido (DAG)

Gráfico de ciclo

Cycle Graph no es lo mismo que el Graph cíclico. En Cycle Graph, cada nodo tendrá exactamente dos bordes conectados, lo que significa que cada nodo tendrá exactamente dos grados.

Aquí hay un ejemplo de un gráfico de ciclo:

Gráfico de ciclo

Gráfica bipartita

Este tipo de Gráficos son tipos especiales de gráficos donde los vértices se asignan a dos conjuntos.

El gráfico bipartito debe seguir la regla:

  • Dos conjuntos de vértices deben ser distintos, lo que significa que todos los vértices deben dividirse en dos grupos o conjuntos.
  • El mismo conjunto de vértices no debe formar aristas.

Gráfica bipartita

Gráfico de Euler

Las estructuras de datos de gráficos se consideran un gráfico de Euler si todos los vértices tienen un grado par. El término grado de vértices significa el número de aristas que apuntan hacia o desde un vértice particular.

Aquí hay un ejemplo de un gráfico de Euler:

Gráfico de Euler

Todos los vértices tienen grados pares. Los vértices A, D, E y H tienen dos grados. Aquí, el nodo C tiene cuatro grados, que es par.

Gráfico de Hamilton

Hamilton Graph es un Connect Graph, donde puede visitar todos los vértices de un vértice determinado sin volver a visitar el mismo nodo o usar el mismo borde. Este tipo de gráfico conectado se conoce como "gráfico de Hamilton". La ruta que visita para verificar si el gráfico dado es un gráfico de Hamilton o no se conoce como ruta hamiltoniana.

Aquí hay un ejemplo gráfico simple de un Hamilton:

Gráfico de Hamilton

En esta imagen, podemos visitar todos los vértices de cualquier nodo en el gráfico anterior. Uno de los caminos puede ser ADCHBE. También es posible encontrar un ciclo de Hamilton. El ciclo de Hamilton comienza y termina en el mismo vértice. Entonces, el ciclo de Hamilton será ADCHBEA.