Tipos de gráficos en estructura de datos con ejemplos
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.

- 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.

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).

- 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:

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:
- 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.
He aquí un ejemplo:

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 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 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 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:
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:
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:
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:
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 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á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á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:
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:
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.