Gráfico (tipo de datos abstracto)
En ciencias de la computación , un gráfico es un tipo de datos abstractos que está destinado a implementar los conceptos de gráficos no dirigidos y gráficos dirigidos del campo de la teoría de gráficos dentro de las matemáticas .
Una estructura de datos de gráfico consta de un conjunto finito (y posiblemente mutable) de vértices (también llamados nodos o puntos ), junto con un conjunto de pares desordenados de estos vértices para un gráfico no dirigido o un conjunto de pares ordenados para un gráfico dirigido. Estos pares se conocen como aristas (también llamados enlaces o líneas ), y para un gráfico dirigido también se conocen como aristas pero también a veces flechas o arcos . Los vértices pueden ser parte de la estructura del grafo o pueden ser entidades externas representadas por índices enteros o referencias .
Una estructura de datos de gráfico también puede asociar a cada borde algún valor de borde , como una etiqueta simbólica o un atributo numérico (costo, capacidad, longitud, etc.).
La siguiente tabla da el costo de complejidad de tiempo de realizar varias operaciones en gráficos, para cada una de estas representaciones, con | V | el número de vértices y | mi | el número de aristas. [ cita requerida ] En las representaciones matriciales, las entradas codifican el costo de seguir un borde. Se supone que el costo de los bordes que no están presentes es ∞.
Las listas de adyacencia generalmente se prefieren para la representación de gráficos dispersos , mientras que se prefiere una matriz de adyacencia si el gráfico es denso; es decir, el número de aristas | mi | está cerca del número de vértices al cuadrado, | V | 2 , o si uno debe poder mirar hacia arriba rápidamente si hay un borde que conecta dos vértices. [5] [6]
La paralelización de problemas de grafos enfrenta desafíos significativos: Cálculos basados en datos, problemas no estructurados, mala localidad y alta proporción de acceso a datos y cómputo. [7] [8] La representación gráfica utilizada para arquitecturas paralelas juega un papel importante para enfrentar esos desafíos. Las representaciones elegidas incorrectamente pueden aumentar innecesariamente el costo de comunicación del algoritmo, lo que disminuirá su escalabilidad . A continuación, se consideran las arquitecturas de memoria compartida y distribuida.
