6.2 Representación de los grafos

6.2 Representación de los grafos

Representación de grafos

Existen diferentes formas de representar un  grafo, y hay muchos métodos para almacenarlos en una computadora. La estructura de datos usada dependerá de las características del grafo, y el algoritmo usado para manipularlo. Entre las más comunes esta las listas y matrices, con frecuencia se usa una combinación de ambas.

Estructura de lista

Lista de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Lista de adyacencia: El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.

Lista de grados: También llamada secuencia de grados o sucesión gráfica de un una secuencia de números, que corresponde a los grados de los vértices del grafo.

Estructuras matriciales

Matriz de adyacencia: El grafo está representado por una matriz cuadrada M de tamaño n^2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento m_ {x, y} es 1, de lo contrario, es 0.

Matriz de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [vértice, arista] contiene la información de la arista (1 - conectado, 0 - no conectado)