Gráfico (tipo de datos abstractos)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Un gráfico dirigido con tres vértices (círculos azules) y tres bordes (flechas negras).

En informática, un gráfico es un tipo de datos abstracto que está destinado a implementar los conceptos de gráfico no dirigido y gráfico dirigido del campo de la teoría de grafos 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. i> pero también a veces flechas o arcos. Los vértices pueden ser parte de la estructura del gráfico o pueden ser entidades externas representadas por índices o referencias enteras.

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 (coste, capacidad, longitud, etc.).

Operaciones

Las operaciones básicas proporcionadas por una estructura de datos de gráfico G generalmente incluyen:

adyacente(G, x, Sí.): prueba si hay un borde del vértice x al vertex Sí.;
vecinos(G, x): lista todos los vértices Sí. tal que hay un borde del vértice x al vertex Sí.;
add_vertex(G, x): añade el vértice x, si no está allí;
remove_vertex(G, x): quita el vértice x, si está allí;
add_edge(G, x, Sí., z): añade el borde z del vértice x al vertex Sí., si no está allí;
remove_edge(G, x, Sí.): quita el borde del vértice x al vertex Sí., si está allí;
get_vertex_value(G, x): devuelve el valor asociado con el vértice x;
set_vertex_value(G, x, v): establece el valor asociado con el vértice x a v.

Las estructuras que asocian valores a los bordes generalmente también proporcionan:

get_edge_value(G, x, Sí.): devuelve el valor asociado con el borde (x, Sí.);
set_edge_value(G, x, Sí., v): establece el valor asociado con el borde (x, Sí.) a v.

Estructuras de datos comunes para representación gráfica

Lista de adyacencia: Los vértices se almacenan como registros o objetos, y cada vértice almacena una lista de vértices adyacentes. Esta estructura de datos permite el almacenamiento de datos adicionales en los vértices. Los datos adicionales se pueden almacenar si los bordes también se almacenan como objetos, en cuyo caso cada vértice almacena sus bordes de incidentes y cada borde almacena sus vértices de incidentes.
Matriz de Adjacency: Una matriz bidimensional, en la que las filas representan vértices fuente y columnas representan vértices destino. Los datos sobre bordes y vértices deben almacenarse externamente. Sólo el costo de un borde se puede almacenar entre cada par de vértices.
Matriz de incidencia: Una matriz bidimensional, en la que las filas representan los vértices y columnas representan los bordes. Las entradas indican la relación de incidencia entre el vértice en una fila y borde en una columna.

El siguiente cuadro proporciona el coste de la complejidad del tiempo de realizar diversas operaciones en gráficos, para cada una de estas representaciones, con TENVTENIENDO el número de vérticesEMantener el número de bordes. En las representaciones de la matriz, las entradas codifican el costo de seguir un borde. El costo de los bordes que no están presentes se supone que son ∞.

	Lista de adyacencia	Matriz de Adjacency	Matriz de incidencia
Gráfico de tiendas	${displaystyle O(vivienda)$	${displaystyle O {fnMicrosoft Sans Serif}$	${displaystyle O(vivir a la muerte)}$
Agregar vértice	${displaystyle O(1)}$	${displaystyle O {fnMicrosoft Sans Serif}$	${displaystyle O(vivir a la muerte)}$
Añadir borde	${displaystyle O(1)}$	${displaystyle O(1)}$	${displaystyle O(vivir a la muerte)}$
Quitar el vértice	${displaystyle O(viviendas)}$	${displaystyle O {fnMicrosoft Sans Serif}$	${displaystyle O(vivir a la muerte)}$
Quitar el borde	${displaystyle O(vivienda)}$	${displaystyle O(1)}$	${displaystyle O(vivir a la muerte)}$
Son vértices x y Sí. adyacente (asumiendo que sus posiciones de almacenamiento son conocidas)?	${displaystyle O(vivienda)}$	${displaystyle O(1)}$	${displaystyle O(viviendas)}$
Observaciones	Lenta para quitar vértices y bordes, porque necesita encontrar todos los vértices o bordes	Lenta para añadir o eliminar los vértices, porque la matriz debe ser redimensionada/copiada	Lenta para añadir o eliminar vértices y bordes, porque la matriz debe ser redimensionada/copada

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 |E| está cerca del número de vértices al cuadrado, |V|², o si uno debe poder buscar rápidamente hacia arriba si hay un borde que conecta dos vértices.

Representación más eficiente de conjuntos de adyacencia

La complejidad temporal de las operaciones en la lista de adjacency puede mejorarse mediante el almacenamiento de los conjuntos de vértices adyacentes en estructuras de datos más eficientes, como tablas de hash o árboles de búsqueda binaria equilibradas (la última representación requiere que los vértices sean identificados por elementos de un conjunto ordenado linealmente, como enteros o cadenas de caracteres). Una representación de vértices adyacentes a través de tablas de hash conduce a una complejidad temporal amortizada promedio ${displaystyle O(1)}$ para probar la adyacencia de dos vértices dados y para eliminar un borde y una complejidad media amortizada del tiempo ${displaystyle O(deg(x)}$ para eliminar un vértice dado $x$ grado ${displaystyle deg(x)}$ . La complejidad temporal de las otras operaciones y el requisito espacial asintotico no cambian.

Representaciones paralelas

La paralelización de problemas de gráficos enfrenta desafíos importantes: cálculos basados en datos, problemas no estructurados, localidad deficiente y una alta proporción de acceso a datos para cálculo. La representación gráfica utilizada para arquitecturas paralelas juega un papel importante a la hora de afrontar esos desafíos. Las representaciones mal elegidas 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.

Memoria compartida

En el caso de un modelo de memoria compartida, las representaciones gráficas utilizadas para el procesamiento paralelo son las mismas que en el caso secuencial, ya que el acceso paralelo de solo lectura a la representación gráfica (por ejemplo, una lista de adyacencia) es eficiente en la memoria compartida.

Memoria distribuida

En el modelo de memoria distribuido, el enfoque habitual es dividir el conjunto de vertex ${displaystyle V}$ del gráfico en ${displaystyle p}$ sets ${displaystyle V_{0},dotsV_{p-1}$ . Aquí, ${displaystyle p}$ es la cantidad de elementos de procesamiento disponibles (PE). Las particiones de conjunto de vértice se distribuyen a los PE con índice de emparejamiento, además de los bordes correspondientes. Cada PE tiene su propia representación subgramática, donde los bordes con un punto final en otra partición requieren especial atención. Para interfaces de comunicación estándar como MPI, el ID del PE poseendo el otro punto final tiene que ser identificable. Durante la computación en un algoritmo de gráficos distribuidos, pasar información a lo largo de estos bordes implica comunicación.

La partición del gráfico debe realizarse con cuidado: existe un equilibrio entre una comunicación baja y una partición de tamaño uniforme. Pero dividir un gráfico es un problema NP-difícil, por lo que no es factible calcularlos. En cambio, se utilizan las siguientes heurísticas.

Partición 1D: Cada procesador consigue ${displaystyle No.$ vértices y los bordes salientes correspondientes. Esto se puede entender como una descomposición de la matriz de adjacency en sentido de fila o columna. Para algoritmos que operan en esta representación, esto requiere un paso de comunicación de todo a todo, así como ${displaystyle {mathcal}(m)}$ tamaños de buffer de mensaje, ya que cada PE potencialmente tiene bordes salientes a cada otro PE.

2D partición: Cada procesador obtiene una submatrix de la matriz adjacency. Suponga que los procesadores están alineados en un rectángulo ${displaystyle p=p_{r}times P_{c}$ , donde ${displaystyle p_{r}$ y ${displaystyle P_{c}$ son la cantidad de elementos de procesamiento en cada fila y columna, respectivamente. Entonces cada procesador obtiene una submatrix de la matriz de adyacencia de la dimensión ${displaystyle (n/p_{r})times (n/p_{c}}$ . Esto se puede visualizar como un patrón de checkerboard en una matriz. Por lo tanto, cada unidad de procesamiento sólo puede tener bordes salientes a PE en la misma fila y columna. Esto limita la cantidad de socios de comunicación para cada PE a ${displaystyle P_{r}+p_{c}-1}$ fuera de ${displaystyle p=p_{r}times P_{c}$ posibles.

Representaciones comprimidas

Los gráficos con trillones de bordes se producen en el aprendizaje automático, análisis de redes sociales y otras áreas. Se han desarrollado representaciones gráficas comprimidas para reducir los requisitos de I/O y memoria. Técnicas generales como la codificación Huffman son aplicables, pero la lista de adjacency o la matriz de adjacency se pueden procesar de maneras específicas para aumentar la eficiencia.

Traversal de Gráficos

Búsqueda primero en amplitud y primera búsqueda en profundidad

La búsqueda en amplitud (BFS) y la búsqueda en profundidad (DFS) son dos enfoques estrechamente relacionados que se utilizan para explorar todos los nodos en un componente conectado determinado. Ambos comienzan con un nodo arbitrario, la "raíz".

Más resultados...