in

Estructura de datos: estructura de datos del gráfico

graph basics

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 como vértices, y los enlaces que conectan los vértices se llaman bordes.

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

Conceptos básicos de gráficos

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 una gráfica usando una matriz de vértices y una matriz bidimensional de aristas. Antes de continuar, familiaricémonos con algunos términos importantes:

  • Vértice – 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 se puede identificar por el índice 0. B puede identificarse usando el índice 1 y así sucesivamente.

  • Borde – El borde representa una ruta 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.

  • Proximidad – 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.

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

grafico

Operaciones básicas

A continuación se muestran las operaciones primarias básicas de un gráfico:

  • Agregar vértice – Agrega un vértice al gráfico.

  • Agregar borde – Agrega un borde entre los dos vértices del gráfico.

  • Vértice de visualización – 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.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

software engineering agile model

Modelo ágil (ingeniería de software) – javatpoint

apple touch icon@2

regex – Java; ¿Reemplazo de cadena (usando expresiones regulares)?