Tipos de gráficos en estructura de datos con ejemplos
sarah chen
⚡ Resumen inteligente
En las estructuras de datos, los grafos son colecciones no lineales de vértices y aristas que se clasifican en familias como grafos dirigidos, no dirigidos, ponderados, cíclicos, acíclicos, completos, conectados, bipartitos, de Euler y de Hamilton, según su estructura.
Un grafo es una estructura de datos no lineal compuesta por vértices y aristas. Los vértices contienen la información o los datos, y las aristas funcionan como un enlace entre un par de vértices.
Los grafos pueden ser de varios tipos, dependiendo de la posición de los nodos y las aristas. A continuación, se muestran algunos tipos importantes de grafos:
Gráfico dirigido
Las aristas del grafo dirigido contienen flechas que indican la dirección. La flecha determina hacia dónde apunta o termina la arista. Aquí hay un ejemplo de un grafo dirigido.
Gráfico dirigido
- Podemos ir del Nodo A al D.
- Sin embargo, no podemos ir del nodo D al nodo A, ya que la arista 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
Un grafo no dirigido contiene aristas sin punteros. Esto significa que podemos viajar en sentido inverso entre dos vértices. Aquí tenemos un ejemplo sencillo de un grafo no dirigido.
Gráfico no dirigido
En el gráfico anterior,
- Podemos movernos de A a B.
- También podemos pasar de B a A.
- Los bordes no contienen direcciones.
Es un ejemplo de un grafo no dirigido que tiene un número finito de vértices y aristas sin pesos.
Gráfico ponderado
Un grafo que contiene pesos o costos en sus aristas se denomina grafo ponderado. El valor numérico generalmente representa el costo de movimiento de un vértice a otro. Tanto los grafos dirigidos como los no dirigidos pueden tener pesos en sus aristas. Aquí se muestra un ejemplo de un grafo ponderado (dirigido).
Gráfico dirigido con peso
- De A a B hay una arista, y el peso es 5, lo que significa que movernos de A a B nos costará 5.
- A apunta a B, pero en este grafo, B no tiene ninguna arista directa sobre A. Por lo tanto, no podemos viajar de B a A.
- Sin embargo, si queremos ir de A a F, hay varios caminos. Los caminos son ADF y ABF. ADF costará (10+11) o 21.
- Aquí, el camino ABF costará (5+15) o 20. Aquí estamos sumando el peso de cada arista en el camino.
Aquí hay un ejemplo de un grafo no dirigido con pesos:
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 grafos bidireccionales y no dirigidos tienen una propiedad común. Es decir:
- Generalmente, un grafo no dirigido puede tener una arista 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.
Aquí hay un ejemplo:
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 grafo contendrá un número infinito de aristas y nodos. Si un grafo es infinito y además conexo, también contendrá un número infinito de aristas. En este caso, las aristas extendidas significan que podrían conectarse más aristas a estos nodos mediante aristas. He aquí un ejemplo de un grafo infinito:
Gráfico infinito
Gráfico nulo
Un grafo nulo contiene únicamente nodos o vértices, pero no aristas. Si se le da un grafo G = (V, E), donde V son los vértices y E son las aristas, será nulo si el número de aristas E es cero. He aquí un ejemplo de un grafo nulo:
Gráfico nulo
Gráfico trivial
Una estructura de datos de grafo se considera trivial si solo tiene un vértice o nodo y ninguna arista. Aquí hay un ejemplo de un grafo trivial:
Gráfico múltiple
Un grafo se denomina multigrafo cuando existen múltiples aristas entre dos vértices, o cuando un vértice forma un bucle. El término "bucle" en la estructura de datos de grafos se refiere a una arista que apunta al mismo nodo o vértice. Un multigrafo puede ser dirigido o no dirigido. A continuación, se muestra un ejemplo de multigrafo:
Hay dos aristas de B a A. Además, el vértice E tiene un bucle. El grafo anterior es un grafo dirigido sin pesos en las aristas.
Gráfico completo
Un grafo es completo si cada vértice tiene aristas dirigidas o no dirigidas con todos los demás vértices. Supongamos que hay un total de V vértices y que cada vértice tiene exactamente V-1 aristas. En ese caso, este grafo se denomina grafo completo. En este tipo de grafo, cada vértice está conectado a todos los demás vértices mediante aristas. A continuación, se muestra un ejemplo de un grafo completo con cinco vértices:
En la imagen se puede observar que el número total de nodos es cinco, y todos los nodos tienen exactamente cuatro aristas.
Gráfico conectado
Un grafo se denomina grafo conexo si, partiendo de un nodo o vértice, podemos recorrer todos los nodos desde ese punto. Para ello, debe existir al menos una arista entre cada par de nodos o vértices. A continuación, se muestra un ejemplo de grafo conexo:
Aquí se ofrece una explicación del grafo conectado anterior:
- Suponiendo que no exista ninguna arista entre C y F, no podemos viajar de A a G. Sin embargo, la arista que conecta C con F nos permite viajar a cualquier nodo desde un nodo dado.
- 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 grafo es cíclico si presenta uno o más ciclos. Aquí hay un ejemplo de un grafo cíclico:
Aquí, los vértices A, B y C forman un ciclo. Un grafo puede contener múltiples ciclos.
Gráfico acíclico dirigido (DAG)
Un grafo se denomina grafo acíclico dirigido o DAG si no hay ciclos dentro del grafo. El DAG es importante al realizar el Orden topológico o para determinar el orden de ejecución. El DAG también es importante para crear sistemas de planificación o analizar la dependencia de recursos, etc. Sin embargo, el grafo anterior no contiene ningún ciclo. Aquí hay un ejemplo sencillo de un grafo acíclico dirigido (DAG):
Gráfico de ciclo
Un grafo cíclico no es lo mismo que un grafo de ciclo. En un grafo cíclico, cada nodo tendrá exactamente dos aristas conectadas, lo que significa que cada nodo tendrá exactamente dos grados. Aquí hay un ejemplo de un grafo cíclico:
Gráfica bipartita
Este tipo de Gráficos Son tipos especiales de grafos donde los vértices se asignan a dos conjuntos. Un grafo bipartito debe seguir la regla:
- Los dos conjuntos de vértices deben ser distintos, lo que significa que todos los vértices deben dividirse en dos grupos o conjuntos.
- Los vértices del mismo conjunto no deben formar aristas.
Gráfico de Euler
Una estructura de datos de grafo se considera un grafo de Euler si todos sus vértices tienen un grado par. El grado de los vértices se refiere al número de aristas que apuntan hacia o desde un vértice determinado. A continuación, se muestra un ejemplo de un grafo de Euler:
Todos los vértices tienen grados pares. Los vértices A, D, E y H tienen dos grados. En este caso, el nodo C tiene cuatro grados, que es par.
Gráfico de Hamilton
Un grafo hamiltoniano es un grafo conexo, donde se pueden visitar todos los vértices desde un vértice dado sin volver a visitar el mismo nodo ni usar la misma arista. Este tipo de grafo conexo se conoce como «grafo hamiltoniano». El camino que se recorre para verificar si un grafo dado es hamiltoniano o no se conoce como camino hamiltoniano. Aquí hay un ejemplo sencillo de un grafo hamiltoniano:
En esta imagen, podemos visitar todos los vértices de cualquier nodo en el gráfico anterior. Uno de los caminos puede ser ADCHBETambién es posible encontrar un ciclo hamiltoniano. Un ciclo hamiltoniano comienza y termina en el mismo vértice. Por lo tanto, el ciclo hamiltoniano será ADCHBEA.
