Introducción al gráfico en la estructura de datos
Los gráficos son estructuras de datos no lineales que comprenden un conjunto finito de nodos y aristas. Los nodos son los elementos y los bordes son pares ordenados de conexiones entre los nodos.
Observe la palabra no lineal. Una estructura de datos no lineal es aquella en la que los elementos no están dispuestos en orden secuencial. Por ejemplo, una matriz es una estructura de datos lineal porque los elementos están dispuestos uno tras otro. Puede recorrer todos los elementos de una matriz en una sola ejecución. Tal no es el caso con las estructuras de datos no lineales. Los elementos de una estructura de datos no lineal están organizados en múltiples niveles, a menudo siguiendo un patrón jerárquico. Los gráficos no son lineales.
La siguiente palabra a la que prestar atención es finita. Definimos el gráfico para que tenga un número finito y contable de nodos. Este es un término bastante poco agradable. Esencialmente, un gráfico puede tener un número infinito de nodos y aún ser finito. Por ejemplo, un árbol genealógico que se remonta a Adán y Eva. Este es un gráfico relativamente infinito, pero aún es contable y, por lo tanto, se considera finito.
Ejemplo del mundo real
El mejor ejemplo de gráficos en el mundo real es Facebook. Cada persona en Facebook es un nodo y está conectado a través de bordes. A es amigo de B. B es amigo de C y así sucesivamente.
Terminologías
Aquí están las Terminologías del Gráfico en la Estructura de Datos que mencionamos a continuación
1. Representación gráfica: generalmente, una gráfica se representa como un par de conjuntos (V, E). V es el conjunto de vértices o nodos. E es el conjunto de bordes. En el ejemplo anterior,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Nodo o vértice: los elementos de un gráfico están conectados a través de bordes.
3. Bordes: una ruta o una línea entre dos vértices en un gráfico.
4. Nodos adyacentes: dos nodos se llaman adyacentes si están conectados a través de un borde. En el ejemplo anterior, el nodo A es adyacente a los nodos B, C y D, pero no al nodo E.
5. Ruta: la ruta es una secuencia de aristas entre dos nodos. Es esencialmente un recorrido que comienza en un nodo y termina en otro. En el ejemplo anterior, hay múltiples rutas desde el nodo A al nodo E.
Ruta (A, E) = (AB, BE)
O
Ruta (A, E) = (AC, CD, DE)
O
Ruta (A, E) = (AD, DE)
6. Gráfico no dirigido : Un gráfico no dirigido es aquel en el que los bordes no especifican una dirección particular. Los bordes son bidireccionales.
Ejemplo
Por lo tanto, en este ejemplo, el borde AC puede atravesarse de A a C y de C a A. Similar a todos los bordes. Una ruta del nodo B al nodo C sería (BA, AC) o (BD, DC).
7. Gráfico dirigido: Un gráfico dirigido es aquel en el que los bordes se pueden atravesar solo en una dirección específica.
Ejemplo
Por lo tanto, en el mismo ejemplo, ahora los bordes son direccionales. Solo puede atravesar el borde a lo largo de su dirección. No hay una ruta desde el nodo B al nodo C ahora.
8. Gráfico ponderado: Un gráfico ponderado es aquel en el que los bordes están asociados con un peso. Este es generalmente el costo para atravesar el borde.
Ejemplo
Por lo tanto, en el mismo ejemplo, ahora los bordes tienen un cierto peso asociado a ellos. Hay dos caminos posibles entre el nodo A al nodo E.
Ruta1 = (AB, BD, DE), Peso1 = 3 + 2 + 5 = 10
Ruta2 = (AC, CD, DE), Peso2 = 1 + 3 + 5 = 9
Claramente, uno preferiría Path2 si el objetivo es alcanzar el nodo E desde el nodo A con un costo mínimo.
Operaciones básicas en gráfico
Aquí están las operaciones básicas del gráfico que se mencionan a continuación
1. Agregar / Eliminar Vértice
Esta es la operación más simple en el gráfico. Simplemente agrega un vértice a un gráfico. No necesita estar conectado a ningún otro vértice a través de un borde. Al eliminar un vértice, debe eliminar todos los bordes que se originan y terminan en el vértice eliminado.
2. Agregar / quitar borde
Esta operación agrega o elimina un borde entre dos vértices. Cuando se eliminan todos los bordes que se originan y terminan en un vértice, el vértice se convierte en un vértice aislado.
3. Breadth-First Search (BFS)
Esta es una operación transversal en el gráfico. BFS atraviesa horizontalmente el gráfico. Esto significa que atraviesa todos los nodos en un solo nivel antes de pasar al siguiente nivel.
El algoritmo BFS comienza en la parte superior del primer nodo del gráfico y luego atraviesa todos los nodos adyacentes. Una vez que se atraviesan todos los nodos adyacentes, el algoritmo repite el mismo procedimiento para los nodos secundarios.
Ejemplo
Atravesar el gráfico anterior en forma BFS resultaría de A -> B -> C -> D -> E -> F -> G. El algoritmo comienza desde el nodo A y atraviesa todos sus nodos adyacentes B, C y D. Marca los cuatro nodos visitados. Una vez que se atraviesan todos los nodos adyacentes de A, el algoritmo se mueve al primer nodo adyacente de A y repite el mismo procedimiento. En este caso, el nodo es B y los nodos adyacentes a B son E y F. A continuación, los nodos adyacentes a C se atraviesan. Una vez que se visitan todos los nodos, la operación finaliza.
4. Profundidad de la primera búsqueda (DFS)
La primera búsqueda de profundidad o DFS atraviesa el gráfico verticalmente. Comienza con el nodo raíz o el primer nodo del gráfico y atraviesa todos los nodos secundarios antes de pasar a los nodos adyacentes.
Ejemplo
Atravesar el gráfico anterior en forma BFS resultaría de A -> B -> E -> F -> C -> G -> D. El algoritmo comienza desde el nodo A y atraviesa todos sus nodos secundarios. Tan pronto como se encuentra con B, parece que tiene más nodos secundarios. Entonces, los nodos secundarios de B se atraviesan antes de pasar al siguiente nodo secundario de A.
Implementaciones de gráficos en el mundo real
- Diseño de circuitos eléctricos para transmisión de potencia.
- Diseño de red de computadoras interconectadas.
- Estudio de la estructura molecular, química y celular de cualquier sustancia, por ejemplo, ADN humano.
- Diseño de rutas de transporte entre ciudades y lugares dentro de una ciudad.
Conclusión: gráfico en la estructura de datos
Los gráficos son un concepto muy útil en estructuras de datos. Tiene implementaciones prácticas en casi todos los campos. Es muy importante comprender los conceptos básicos de la teoría de gráficos, para desarrollar una comprensión de los algoritmos de la estructura gráfica.
Este artículo fue simplemente una introducción a los gráficos. Es solo un trampolín. Se recomienda profundizar más en el tema de la teoría de grafos.
Artículos recomendados
Esta es una guía para el gráfico en la estructura de datos. Aquí discutimos las Terminologías y Operaciones Básicas del Gráfico en la Estructura de Datos. También puede consultar el siguiente artículo para obtener más información:
- Preguntas de la entrevista de estructura de datos
- Modelo de datos en Cassandra
- ¿Qué es Data Mart?
- ¿Qué es un científico de datos?