Estructura de datos: estructura de datos del gráfico

Un gráfico es una representación pictórica de un conjunto de objetos donde algunos pares de objetos están conectados por enlaces. Los objetos interconectados están representados por puntos denominados comovertices, y los enlaces que conectan los vértices se llaman edges.

Formalmente, una gráfica es un par de conjuntos (V, E), dónde V es el conjunto de vértices y Ees el conjunto de aristas, que conecta los pares de vértices. Eche un vistazo al siguiente gráfico:

En el gráfico anterior,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Estructura de datos del gráfico

Los gráficos matemáticos se pueden representar en la estructura de datos. Podemos representar un gráfico usando una matriz de vértices y una matriz bidimensional de aristas. Antes de continuar, familiaricémonos con algunos términos importantes:

• Vertex- Cada nodo del gráfico se representa como un vértice. En el siguiente ejemplo, el círculo etiquetado representa vértices. Por tanto, A a G son vértices. Podemos representarlos usando una matriz como se muestra en la siguiente imagen. Aquí, A puede identificarse mediante el índice 0. B se puede identificar mediante el índice 1 y así sucesivamente.

• Edge- El borde representa un camino entre dos vértices o una línea entre dos vértices. En el siguiente ejemplo, las líneas de A a B, B a C y así sucesivamente representan bordes. Podemos usar una matriz bidimensional para representar una matriz como se muestra en la siguiente imagen. Aquí AB se puede representar como 1 en la fila 0, columna 1, BC como 1 en la fila 1, columna 2 y así sucesivamente, manteniendo otras combinaciones como 0.

• Adjacency- Dos nodos o vértices son adyacentes si están conectados entre sí a través de un borde. En el siguiente ejemplo, B es adyacente a A, C es adyacente a B, y así sucesivamente.

• Path- Path representa una secuencia de aristas entre los dos vértices. En el siguiente ejemplo, ABCD representa una ruta de A a D.

Operaciones básicas

Las siguientes son operaciones primarias básicas de un gráfico:

• Add Vertex - Agrega un vértice al gráfico.

• Add Edge - Agrega un borde entre los dos vértices del gráfico.

• Display Vertex - Muestra un vértice del gráfico.

Para saber más sobre Graph, lea el Tutorial de teoría de gráficos . Aprenderemos cómo atravesar un gráfico en los próximos capítulos.