PDF de programación - Estructuras de datos: Grafos

Estructuras de datos: Grafos

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Grafos

Grafos

Un grafo es un par G = (V , A).

V es el conjunto de vértices o nodos.
A es el conjunto de aristas.

Cada arista es un par (v, w) ∈ V .
Si el par está ordenado, entonces el grafo es dirigido.

Principales representaciones de grafos dirigidos:

Matriz de adyacencia.
Listas de adyacencia.

Algoritmos

Grafos

Matriz de adyacencia

Es una matriz bidimensional.
Para cada arista (u, v), se pone a[u, v] = 1; en caso contrario,
el contenido es 0.
Si la arista tiene un peso asociado,

se pone en a[u, v] el peso, y
se usa un peso muy grando o muy pequeño como centinela
indicando la inexsistencia de aristas.
Requerimiento de espacio: Q (|V|2).

Resulta adecuado para grafos densos,
pero prohibitivo si el grafo es disperso.

Algoritmos

Grafos

Listas de adyacencia

Para cada vértice mantenemos una lista
de todos sus vértices adyacentes.

La representación conisistirá en un vector de listas de adyacencia.

Requerimiento de espacio: Q (|A| +|V|).
Buena solución para grafos dispersos.

Si el grafo no fuese dirigido,

Cada arista (u, v) aparecería en dos listas,
duplicándose el espacio en uso.

Algoritmos

Grafos

Consideraciones

Problema común en los algoritmos de grafos: encontrar
los nodos adyacentes a un nodo dado.

Ambas representaciones consiguen buenos resultados,

recorriendo una fila o columna de la matriz de adyacencia, o
recorriendo la lista de adyacencia apropiada.

En la mayoría de aplicaciones, los vértices tienen nombres,
desconocidos en tiempo de compilación, en vez de números.

La forma más sencilla de dar una correspondencia entre nombres
y números es usar una tabla de dispersión.

Algoritmos

Grafos