Teoría de Grafos en Estructuras de Datos: Conceptos, Tipos y Algoritmos de Recorrido

Conceptos Fundamentales de Grafos

GRAFOS: Tipos:

• Grafos no dirigidos: Las aristas no están ordenadas.
• Grafos dirigidos: Las aristas son pares ordenados, existe una cola y una cabeza de arista. Se denominan dígrafos.

Nodos adyacentes a un nodo v: Todos los nodos unidos a v mediante una arista. Un grafo está etiquetado si cada arista tiene asociada una etiqueta o valor de cierto tipo. Grafo con pesos: grafo etiquetado con valores numéricos.

Un grafo es conexo (o conectado) si hay un camino entre cualquier par de vértices.

• Camino simple: Aquel en el que todos los vértices son distintos.
• Ciclo: Es un camino en el cual el primer y el último vértice son iguales.
• Grafo completo: Si existe una arista entre cualquier par de vértices.

Grado de un vértice v: Número de arcos que inciden en él.

Recorridos en Grafos

• Búsqueda en profundidad: Equivalente a un recorrido en preorden de un árbol. El conjunto de nodos marcados se trata como una pila.
• Búsqueda en amplitud o anchura: Equivalente a recorrer un árbol por niveles. El conjunto de nodos marcados se trata como una cola.

Algoritmo de Anchura

1. Marcar el vértice de partida v.
2. Meter en la cola el vértice de partida v.
3. Repetir los pasos 4 y 5 hasta que se cumpla la condición de cola vacía.
4. Quitar el nodo frente de la cola y comprobar su adyacencia.
5. Introducir en la cola los vértices adyacentes que no estén marcados, y marcar estos vértices.
6. Fin del proceso.

Algoritmo de Profundidad

1. Marcar el vértice de partida v.
2. Meter en la pila el vértice de partida v.
3. Repetir los pasos 4 y 5 hasta que se cumpla la condición de pila vacía.
4. Quitar el nodo correspondiente de la pila y comprobar su adyacencia.
5. Introducir en la pila los vértices adyacentes que no estén marcados, y marcar estos vértices.
6. Fin del proceso.

Algoritmos Avanzados y Aplicaciones

Ordenación Topológica

1. Buscar un vértice sin predecesores (se calcula el grado de entrada de todos los vértices y los que cumplan esta condición se introducen en la cola).
2. Este vértice v pasa a formar parte de la ordenación (tratar el frente de la cola; cuando se procesa v, el grado de entrada de todos los adyacentes se decrementa en una unidad, y aquellos que tienen grado de entrada 0 se introducen en la cola).

Algoritmo de Floyd

Con Dijkstra conocemos el camino mínimo para un nodo, pero en ocasiones podemos necesitar conocerlo para todos los nodos. Opción sencilla: Dijkstra para todos los vértices. El objetivo es crear una matriz D[i,j] donde el elemento i,j contenga el camino mínimo entre los vértices i e j.

Prim (Árbol de Expansión de Coste Mínimo)

Dado un grafo no dirigido, crear a partir de él un árbol con todos los vértices unidos y de mínimo coste.