Estructuras de datos y algoritmos

Tutorial de estructura de datos de gráficos

Tutorial de estructura de datos de gráficos
En informática, un gráfico es un conjunto de nodos conectados por enlaces. La principal diferencia entre un árbol y un gráfico es que un árbol tiene un nodo raíz, mientras que un gráfico tiene más de un nodo raíz. Ya debe tener un conocimiento básico de la estructura de datos de árbol antes de venir aquí, ya que los conceptos allí se usarán aquí con poca o ninguna explicación. Si no tiene ese conocimiento, lea el tutorial titulado, Tutorial de estructura de datos de árbol para principiantes, en el enlace, https: // linuxhint.com / tree_data_structure_tutorial_beginners /.

Un nodo en un gráfico se llama vértice (plural - vértices). A veces todavía se le llama nodo; también se puede llamar un punto. Un vínculo en un gráfico se llama borde. A veces todavía se le llama enlace; también se puede llamar una línea.

Gráfico con muchas características

Esta figura muestra un gráfico con muchas características:

Los círculos (discos) son vértices. Cualquier línea recta o curva o bucle es un borde.

Características del gráfico

Vértice

Un vértice es un objeto. Puede ser una casa; puede ser una persona; puede ser un sustantivo abstracto; puede ser cualquier objeto que se te ocurra.

Borde

Un borde es una conexión (relación) entre dos vértices; la conexión puede ser abstracta.

Círculo

Un bucle es una arista que conecta un vértice consigo mismo.

Borde de la flecha

Considere dos personas: Juan y Pedro. Si John le presta a Peter $ 100, y si John y Peter son vértices, entonces la ventaja del préstamo apuntará hacia Peter. Si ambos socios olvidan que Peter le debe a John, y Peter le presta a John $ 100, entonces en el otro extremo del mismo borde, una punta de flecha apuntará hacia John. Si Peter le prestó $ 75 a John y no $ 100, entonces una ventaja diferente conectaría a Peter con John. Este segundo borde tendrá su punta de flecha apuntando hacia John. En el segundo caso, hay dos bordes, con una punta de flecha cada uno, apuntando en direcciones opuestas.

El vértice al que apunta una arista, es un vértice de cabeza para esa arista. El vértice del que sale un borde, es un vértice de cola.

Incidente

Un borde conecta dos vértices. Se dice que el borde incide en cualquier vértice. El borde no necesita tener punta de flecha. Los dos vértices se conocen como los puntos finales del borde. Es posible tener un gráfico donde un vértice no pertenece a ningún borde, pero eso no se considerará en este tutorial.

Gráfico no dirigido

Un borde puede ser una flecha o no. Un gráfico donde ningún borde es una flecha es un gráfico no dirigido. Un borde puede estar representado por una línea recta, una curva o un bucle.

Gráfico dirigido

Un gráfico donde cada borde es una flecha (dirección) es un gráfico dirigido. El borde de una flecha se puede representar mediante una línea recta con una punta de flecha o una curva con una punta de flecha o un bucle con una punta de flecha.

La ausencia de una dirección en el borde de un gráfico no dirigido significa que cada borde del gráfico no dirigido es bidireccional.

Grado de un vértice

El número de aristas que inciden en un vértice es el grado del vértice. Un bucle tiene dos incidencias en un vértice, por lo que un bucle se cuenta dos veces.

Orden de un gráfico

El orden de una gráfica es el número de vértices en la gráfica.

Multigraph

Un multigraph es un gráfico, donde para algunos pares de vértices, hay más de una arista. Un multigraph no dirigido es un gráfico en el que los bordes no tienen direcciones (no son flechas). Un multigraph dirigido es aquel donde cada borde es una flecha, y para pares de vértices que tienen más de una flecha, un vértice es la cola de esas flechas y el otro vértice es la cabeza de las mismas flechas. El siguiente diagrama muestra un multigraph no dirigido:

Más de una arista (i.mi. múltiples aristas) para un par de vértices también se denominan aristas paralelas.

Carcaj

Un carcaj es un multigraph que permite bucles (uno o más bucles). Algunos multigraphs no permiten bucles.

Gráfico simple

Un gráfico simple es un gráfico en el que no hay dos pares de vértices que tengan múltiples aristas. No se permiten bucles en un gráfico simple.

Gráfico vacío

Un gráfico vacío es un gráfico sin vértices y, por lo tanto, sin bordes.

Gráfico mixto

Un gráfico mixto es un gráfico en el que algunos bordes son flechas y otros no; en otras palabras: algunos bordes tienen direcciones y otros no están dirigidos.

Gráfico ponderado

Es posible tener un gráfico en el que se asigne un número, conocido como peso, a cada borde. Algunas aristas tienen el mismo número, pero los números son generalmente diferentes. Este gráfico se llama gráfico ponderado. Los números de un gráfico en particular pueden representar longitudes o costos (precios) o magnitud de algún tipo, según el problema.

Indegree y Outdegree

El vocabulario, el grado y el grado superior son aplicables solo a un gráfico dirigido. El gráfico puede ser o no multigraph. El gráfico puede tener o no bucles.

El número de puntas de flecha conectadas a un vértice es el grado de grado de ese vértice. Una flecha con una sola punta de flecha tiene un extremo de cabeza y un extremo de cola. El número de colas conectadas a un vértice es el grado exterior de ese vértice.

Nota: Un gráfico con múltiples aristas para el par de vértices, donde las múltiples aristas están en direcciones opuestas, no se aborda en este tutorial.

Representación de software de un gráfico

Un gráfico se puede representar en el software de la forma en que se dibuja en el diagrama. Un gráfico también se puede representar en software mediante una matriz matemática (matriz bidimensional). Una de estas matrices se llama matriz de adyacencia.

Matriz de adyacencia

Una matriz de adyacencia es una matriz cuadrada. Los títulos de las filas son todos los vértices, escritos en orden ascendente. Los encabezados de las columnas siguen siendo los mismos vértices, escritos en orden ascendente. El recuento de filas o columnas de una matriz comienza desde 1 y no desde cero como con las matrices. Al identificar un elemento en una matriz, el número de fila se escribe primero antes del número de columna.

Para un gráfico no dirigido, cada entrada (elemento) en la matriz de adyacencia es el número de aristas que conectan los dos vértices correspondientes. Un bucle debe contarse dos veces. Para un gráfico dirigido, cada entrada en la matriz de adyacencia es el número de aristas que salen de un vértice de fila y entran en el vértice de columna correspondiente o es el número de aristas que salen de un vértice de columna y entran en el vértice de fila correspondiente. La elección es la del programador. En esta situación (en cualquier caso), un bucle debe contarse una vez.

Nota: un gráfico es un diagrama que es una estructura de datos por derecho propio. Una matriz de adyacencia también es una estructura de datos por derecho propio.

Gráfica no dirigida y matriz de adyacencia

Los siguientes diagramas muestran un gráfico no dirigido y la correspondiente matriz de adyacencia:

La diagonal principal de una matriz es la diagonal de arriba a la izquierda a abajo a la derecha. Una matriz no dirigida es simétrica con respecto a la diagonal principal. La entrada de la matriz para la fila A y la columna C es 1, lo que significa que hay un borde que conecta el vértice A y el vértice C. La entrada de la matriz para la fila C y la columna B es 3, lo que significa que hay 3 aristas que conectan el vértice C y el vértice B. Las otras entradas se explican de manera similar.

La suma de las entradas de una fila da el número de aristas (grados) del vértice correspondiente. La suma de las entradas para la fila A es 2, lo que significa que 2 aristas están conectadas al vértice A. La suma de las entradas para la fila B es 6, lo que significa que 6 aristas están conectadas al vértice B. El resto de las entradas se explican de manera similar.

Gráfica dirigida y matriz de adyacencia

Los siguientes diagramas muestran un gráfico dirigido y la correspondiente matriz de adyacencia:

La matriz de adyacencia para un gráfico dirigido no es necesariamente simétrica con respecto a la diagonal principal. La entrada de la matriz para la fila A y la columna C es 1, lo que significa que un borde sale del vértice A al vértice C. La entrada de la matriz para la fila C y la columna B es 3, lo que significa que 3 aristas salen del vértice C al vértice B. Las otras entradas se explican de manera similar.

La suma de las entradas de una columna da el grado de grado del vértice (columna). La suma de las entradas de una fila da el grado de salida del vértice (fila). La suma de las entradas de la columna A es 1, lo que significa que un borde se dirige al vértice A. La suma de las entradas para la fila B es 2, lo que significa que 2 aristas salen del vértice B. El resto de las entradas se explican de manera similar.

Operaciones gráficas

Una estructura de datos, como un gráfico, consta de un conjunto de valores de datos o un conjunto de objetos, más la relación entre los objetos, más las operaciones (funciones) entre los objetos. Las relaciones en un gráfico están indicadas por los bordes. Además, un gráfico debe tener al menos las siguientes operaciones:

adyacente (G, x, y)

G significa gráfico. Esta operación verifica si una arista conecta el vértice xy el vértice y. El valor y la posición de una entrada en una matriz indican la conexión de un borde (y su tipo).

vecinos (G, x)

Esta operación devuelve una lista de todos los vértices que están conectados directamente al vértice x. El valor y la posición de una entrada en una matriz indican la conexión de un borde.

eliminar_vertex (G, x)

Esta operación elimina un vértice, x de un gráfico. Si el vértice no tiene arista, no hay problema. Sin embargo, si el vértice tenía enlaces, entonces los enlaces (bordes) también deberían eliminarse. El valor y la posición de una entrada en una matriz indican la presencia de un vértice particular. Si se elimina un vértice, la matriz debe reajustarse.

add_vertex (G, x)

Esto agrega un vértice, x sin agregar bordes, o reemplaza un vértice que tenía bordes pero se había eliminado. El valor y la posición de una entrada en una matriz indican la presencia de un vértice particular. Si se agrega un vértice, la matriz debe reajustarse.

add_edge (G, x, y)

Esta operación agrega una nueva arista entre el vértice x y el vértice y si la arista no estaba allí. El valor y la posición de una entrada en una matriz indican la presencia de un borde en particular. Si se agrega un borde, la matriz debe reajustarse.

eliminar_borde (G, x, y)

Esta operación eliminaría el borde entre el vértice x y el vértice y si el borde estuviera allí. El valor y la posición de una entrada en una matriz indican la presencia de un borde en particular. Si se quita un borde, la matriz debe reajustarse.

get_vertex_value (G, x)

Esta operación devuelve el valor, v asociado con el vértice, x. Para lograr esto, necesita un conjunto poderoso de subconjuntos para etiquetas de vértice y sus valores.

set_vertex_value (G, x, v)

Esta operación da un nuevo valor, v para el valor asociado con el vértice, x. Para lograr esto, necesita un conjunto poderoso de subconjuntos para etiquetas de vértice y sus valores.

Algunos gráficos también asocian valores a sus bordes. Tales gráficos necesitan las siguientes operaciones adicionales:

get_edge_value (G, x, y)

Esta operación devuelve el valor, v asociado con el borde, (x, y). Para lograr esto, necesita un conjunto de potencias de subconjuntos para los bordes y sus valores.

set_edge_value (G, x, y, v)

Esta operación da un nuevo valor, v para el valor asociado con el borde, (x, y). Para lograr esto, necesita un conjunto de subconjuntos de potencia para los bordes y sus valores.

Conclusión

Un gráfico es un conjunto de vértices conectados con aristas. Un gráfico puede no estar dirigido o dirigido. Los bordes pueden ser unidireccionales o direccionales. Los bucles pueden estar presentes o ausentes en un gráfico. Lo que debe aprender a continuación es el conjunto, el conjunto de potencia y el conjunto múltiple relacionado con los gráficos. Después de eso, debe aprender los diferentes tipos de gráficos, como un gráfico orientado, gráfico regular, gráfico completo, gráfico bipartito, gráfico de torneo, gráfico de red de flujo, etc.

Chrys

Sobre el Autor

Chrysanthus Forcha

Descubridor de la integración matemática de First Principles y series relacionadas. Maestría en Educación Técnica, especialidad en Electrónica y Software de Computación. Licenciatura en Electrónica. También tengo conocimientos y experiencia a nivel de Maestría en Informática y Telecomunicaciones. De 20.000 escritores, fui el 37o mejor escritor en devarticles.com. Trabajo en estos campos desde hace más de 10 años.

Ver todas las publicaciones
SuperTuxKart para Linux
SuperTuxKart es un gran título diseñado para ofrecerte la experiencia Mario Kart de forma gratuita en tu sistema Linux. Es bastante desafiante y diver...
Tutorial de Battle for Wesnoth
The Battle for Wesnoth es uno de los juegos de estrategia de código abierto más populares que puedes jugar en este momento. Este juego no solo ha esta...
0 A.D. Tutorial
De los muchos juegos de estrategia que existen, 0 A.D. logra destacarse como un título completo y un juego táctico muy profundo a pesar de ser de códi...