AED 2: Grafos

Grafos

Son estructuras de datos NO lineales, y se los puede definir como un conjunto de puntos o nodos, y un conjunto de líneas o aristas, tal que cada una de ellas une un punto con otro punto.

Un grafo es una estructura de datos que almacena datos de dos tipos:

Vértices: son objetos que contienen información.

Aristas o arcos: cada uno conecta un vértice con otro, y puede tener un valor almacenado.

Se clasifican en:

Grafos ponderados: cuando las aristas llevan un coste asociado (un entero al que se denomina peso).

Dirigidos: cuando todas las aristas son dirigidas. Es importante el orden del par de nodos que definen cada arista.

No dirigidos: cuando todas las aristas son NO dirigidas. El orden del par de nodos carece de importancia.

Los grafos tienen gran cantidad de aplicaciones: representación de circuitos electrónicos analógicos y digitales, representación de caminos o rutas de transporte en localidades y representación de redes de computadoras.

Grafo conexo y NO conexo

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Y es no conexo cuando no se encuentra un camino entre dos vértices.

1 - Grafo CONEXO. 2 - Grafo NO CONEXO

Representaciones

• Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas.

• En los algoritmos que se aplican sobre ellos veremos que adoptarán tiempos distintos dependiendo de la forma de representación elegida.

• En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso o disperso.

Representación por matriz de adyacencia:

Consiste en una tabla de tamaño V x V, en que la que a[i, j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el valor será 0.

Caso Particulares:

• Cuando se trata de grafos ponderados en lugar de 1 el valor que tomará será el

peso de la arista.

• Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 (o con el

peso) tanto la entrada a[i, j] como la entrada a[j, i], puesto que se puede recorrer

en ambos sentidos.

Matriz de Adyacencia hecho en Pascal:

Representación por lista de adyacencia:

Las listas de adyacencia son estructuras que contendrán un valor entero (el número que identifica al nodo destino), así como otro entero que indica el coste en el caso de que el grafo sea ponderado.

Lista de Adyacencia

Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder.

Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de B aparecerá la correspondiente referencia al nodo A.

El conjunto de vértices se representa como un vector, el cual tiene un número máximo de posiciones que es igual al número máximo de vértices del grafo. También se llena con valores booleanos.

Lista de Adyacencia hecho en Pascal: