Grafos

Grafos
La teoría de grafos estudia las propiedades de los grafos, un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas quepueden ser orientados o no. Un grafo se representa mediante una serie de puntos conectados por líneas.

Estructuras de datos en la representación de grafos
La estructura de datos usada paraalmacenar grafos en una computadora depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices,aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, peropueden consumir grandes cantidades de memoria.

Características de la Estructura de lista
• Lista de incidencia - Las aristas son representadas con un vector de pares que serán ordenados si el grafoes dirigido donde cada par representa una de las aristas.

• Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo nodirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son mas rápidas.

En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista quecontenga todos aquellos vértices j que sean adyacentes a el. De esta forma solo reservara memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. Elgrafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cadaelemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

Estructuras...