Algoritmos De Grafos

Algoritmos de Grafos

Los grafos son solo abstracciones matemáticas, pero son útiles en la práctica porque nos ayudan a resolver numerosos problemas importantes. Estas notas describen algunos de los algoritmos y métodos más conocidos para resolver problemas de procesamiento de grafos, así como proponen alternativas para la representación de los mismos en el computador. Cada algoritmo o método está acompañado de figuras que ilustran su funcionamiento y de una breve descripción teórica que incluye el estudio de la complejidad en tiempo del mismo. En adición se incluye la descripción de una taxonomía de

clasificación de problemas de procesamiento de grafos, basada en el grado de dificultad de

lo mismos.

Estas notas abarcan desde problemas simples como el de recorrido de grafos, hasta problemas más complejos como los de flujo en redes. Es recomendable que el lector tenga conocimientos básicos de estructuras de datos dinámicas y de teoría de grafos.

Palabras Claves: Grafos. Algoritmia. Algoritmos de Grafos. Procesamiento de Grafos.

Estructuras de Datos para Grafos.

CONCEPTOS BASICOS

Hablando intuitivamente, un grafo es un conjunto de nodos unidos por un conjunto de líneas o flechas. Por lo general, los nodos son entes de procesamiento o estructuras que contienen algún tipo de información y las líneas o flechas son conexiones o relaciones entre estos entes. Si se utilizan flechas para conectar los nodos decimos que el grafo es dirigido (también llamado digrafo) porque las relaciones entre los nodos tienen una dirección. En caso contrario el grafo es no dirigido. En cualquiera de los dos casos, bien sea que se utilicen líneas o flechas, a estas relaciones se les puede llamar simplemente aristas.

Frecuentemente las aristas también tienen algún tipo de información asociada (distancia, costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado.

Las secuencias de aristas forman caminos o ciclos. Un ciclo es un camino que termina en el mismo nodo donde comenzó. Si el camino recorre todos los nodos del grafo es llamado tour. El número de aristas en un camino es la longitud del camino.

Se dice que un grafo es conexo si se puede llegar desde cualquier nodo hasta cualquier otro mediante un camino. De lo contrario no es conexo, pero puede dividirse en componentes conexas, que son subconjuntos de nodos y aristas del grafo original que si son conexos. Un grafo conexo sin ciclos es llamado un árbol.

Estos son apenas unos cuantos conceptos de lo que se conoce como la Teoría de Grafos. El objetivo de estas notas no es cubrir por completo dicha teoría sino enfocarnos en la implementación de este tipo de estructuras y las operaciones y algoritmos más comunes e importantes que se aplican sobre las mismas.

REPRESENTACION EN EL COMPUTADOR

Hay por lo menos dos maneras evidentes de representar un grafo en un computador, utilizando la notación seudoformal propuesta en [2]. La primera utiliza lo que se conoce

como una matriz de adyacencia, a saber:

CLASE Grafo

Privado:

Arreglo de <Tipo> Nodos de [1..N];

Arreglo de logico MatrizDeAdyacencia de [1..N][1..N];

Publico:

# Todas las operaciones aquí

FCLASE

Un valor verdadero en la posición (i,j) de la matriz indica que hay una arista que conecta al nodo i con el nodo j. Para representar un grafo pesado se puede cambiar la matriz de adyacencia de lógicos a una matriz de registros, siendo el peso un campo del registro.

Esta representación es muy útil cuando se cumplen dos condiciones principales. Primero, si se conoce el número exacto de nodos en el grafo no hace falta utilizar estructuras dinámicas porque las estáticas se pueden acceder con mayor facilidad. Segundo, la matriz de adyacencia no contiene un gran número de elementos en FALSO. 5Si no se cumple la primera de estas condiciones y el número de nodos en el grafo puede variar drásticamente entonces se justifica el uso de estructuras dinámicas. En este caso, lo ideal es utilizar una lista lineal de nodos conteniendo la información en <Tipo>.

Por supuesto, si el número de nodos va a cambiar entonces tampoco se justificas tener un matriz estáticas, por lo que debería utilizarse una matriz esparcida.

CLASE Nodo #Nodo de la lista de <Tipo>

Publico:

entero Id;

<Tipo> Info;

­Nodo proximo;

#Operaciones aquí

FCLASE

#La declaración de los nodos para las columnas (NodoC), filas (NodoF) y

#nodos internos de la matriz van aquí. Son las declaraciones de una

#matriz esparcida implementada con listas con posición lógica fija o

#relativa.

CLASE Grafo

Privado:

­Nodo primerNodo; # 1er. nodo de la lista

­NodoF primeraFila; # 1era. fila de la matriz esparcida

­NodoC primeraColumna; # 1era. columna de la matriz esparcida

Publico:

# Todas las operaciones aquí

FCLASE

Sin embargo, puede que esta solución no sea la más conveniente por el hecho de que la matriz esparcida ocupará más memoria que su contraparte estática a medida que el número de conexiones entre los nodos sea mayor, ya que habrá pocos elementos no nulos dentro de la matriz. En ese caso, se debe utilizar otra implementación.

CLASE Nodo #Nodo de la lista de <Tipo>

Publico:

entero Id;

<Tipo> Info;

­Nodo proximo;

­Ady ListaDeAdyacentes;

#Operaciones aquí

FCLASE

CLASE Ady #Nodo de la lista de nodos adyacentes

Publico:

­Nodo AdyAeste;

­Ady proximo;

#Operaciones aquí

FCLASE

CLASE Grafo

Privado:

­Nodo primerNodo; # 1er. nodo de la lista

Publico: 6

# Todas las operaciones aquí

FCLASE

Esta representación ocupa menos memoria que la anterior sin importar si la matriz esparcida esta muy llena o no, pero puede incrementar la complejidad de algunas operaciones, como por ejemplo saber cuáles nodos son adyacentes a un nodo en particular (en caso de un grafo dirigido).

De nuevo, si las aristas también tienen algún tipo de información asociada bastaría una leve modificación en la clase Ady estructura para agregarla.

Por supuesto, se deben implementar las operaciones más comunes como agregar un nodo al grafo,

...