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, eliminar un nodo del grafo y conectar un nodo con otro. En adición, se puede implementar todo tipo de operaciones basadas en la teoría de grafos, para resolver los problemas que se describen a continuación.

RECORRIDO DE GRAFOS

Cualquier algoritmo de recorrido de grafos consiste básicamente en visitar un nodo del grafo y luego ir visitando los nodos conectados a este. Este principio se aplica recursivamente comenzando desde un nodo inicial cualquiera del grafo.

Lo que diferencia un algoritmo de recorrido de otro es, una vez ubicado en un nodo en particular, la forma en que se visitan los nodos conectados a este. Por supuesto, estos algoritmos pueden ser aplicados en grafos dirigidos o no dirigidos.

Los dos algoritmos “clásicos” de recorrido de grafos son el recorrido en profundidad y en anchura. Precisamente por ser “clásicos” han sido estudiados con anterioridad y se les conoce su orden de complejidad en tiempo y todos los beneficios de aplicarlos.

Recorrido en profundidad

Para efectuar un recorrido en profundidad de un grafo, se selecciona cualquier nodo como punto de partida (por lo general el primer nodo del grafo) y se marcan todos los nodos del grafo como “no visitados”. El nodo inicial se marca como “visitado” y si hay un nodo adyacente a este que no haya sido “visitado”, se toma este nodo como nuevo punto de partida del recorrido. El recorrido culmina cuando todos los nodos hayan sido visitados.

Se dice que el recorrido es en profundidad, porque para visitar otro nodo adyacente del nodo inicial, primero se deben visitar TODOS los nodos adyacentes al que se eligió antes. Es así, como el número de ambientes recursivos varía dependiendo de la profundidad que alcance el algoritmo.

Agregando el campo logico visitado; en la última implementación de grafos tratada, podríamos implementar el recorrido en profundidad de la siguiente manera:

10

Privado:

ACCION DFS_R(­Nodo Actual)

#se marca el nodo actual como visitado

Actual­.visitado ¬ verdad;

­Ady aux;

aux ¬Actual.­ListaDeAdyacentes;

#se recorre la lista de adyacentes al nodo Actual para

#visitarlos

Mientras ( aux ¹ NULL ) hacer

si ( (aux­.AdyAeste)­.visitado ¹ verdad) entonces

#se hace la llamada recursiva a los nodos

#adyacentes para visitarlos

DFS_R(aux­. AdyAeste);

fsi

aux ¬ aux­.proximo;

fmientras

FACCION

Publico:

ACCION DFS() #Depth-First Search

­Nodo aux;

aux ¬ primerNodo;

#aquí se recorre la lista de nodos iterativamente

#haciendo las llamadas al DFS_R (DFS recursivo) cada vez que

#se consiga a alguien no visitado. Esto se hace para evitar

#que el algoritmo no funcione si el grafo tiene varias com-

#ponentes conexas

mientras (aux ¹ NULL) hacer

si (aux­.visitado ¹ verdad) entonces

DFS_R(aux);

fsi

aux ¬ aux­.proximo;

fmientras

FACCION

Este algoritmo recorre todos los nodos del grafo pero fácilmente puede modificarse para que sea una función que encuentre un nodo en particular dentro de grafo. Este algoritmo se conoce como el algoritmo DFS (Depth-First Search).

Una bondad de este algoritmo es que los nodos solo se vistan una vez. Esto implica que si se salvan en alguna estructura las aristas que se van recorriendo se obtiene un conjunto de aristas de cubrimiento mínimo del grafo, lo cual se utiliza frecuentemente se utiliza para reducir la complejidad del grafo cuando la perdida de información de algunas aristas no es importante. Este resultado se conoce como árbol DFS (DFS Tree).

El algoritmo de recorrido en profundidad tiene orden O(máx(A,N)) donde N es el número de nodos y A es el número de aristas. Esto es porque un grafo de N nodos puede tener más de N aristas, en cuyo caso se ejecutan más de N ciclos en DFS_R, pero si por el contrario hay menos aristas que nodos, de cualquier manera se visitaran todos los nodos en

DFS.

El DFS puede modificarse fácilmente y utilizarse para resolver problemas sencillos como los de conectividad simple, detección de ciclos y camino simple. Por ejemplo, el número de veces que se invoca a la acción DFS_R desde la acción DFS en el algoritmo anterior es exactamente el número de componentes conexas del grafo, lo cual representa la solución al problema de conectividad simple.

Recorrido en anchura

En este algoritmo también se utiliza la estrategia de marcas los nodos como “visitados” para detectar la culminación del recorrido, pero los nodos se recorren de una manera ligeramente distinta.

De nuevo, se selecciona cualquier nodo como punto de partida (por lo general el primer nodo del grafo) y se marcan todos los nodos del grafo como “no visitados”. El nodo inicial se marca como “visitado” y luego se visitan TODOS los nodos adyacentes a este, al finalizar este proceso se busca visitar nodos más lejanos visitando los nodos adyacentes a los nodos adyacentes del nodo inicial.

Este algoritmo puede crear menos ambientes recursivos que el anterior porque visita más nodos en un mismo ambiente, pero esto depende de cómo este construido el grafo. El algoritmo se conoce como el algoritmo de BFS (Breadth-First Search).

Este algoritmo tiene exactamente el mismo orden en tiempo de ejecución del algoritmo de recorrido en profundidad y también se puede obtener el conjunto de aristas de cubrimiento mínimo del grafo.

Una diferencia notable entre el DFS y el BFS es que este último necesita de una estructura auxiliar, que por lo general es una cola, para el almacenamiento de las aristas que se van a visitar durante el recorrido.

El siguiente ejemplo ilustra el funcionamiento del algoritmo BFS sobre un grafo de ejemplo. La secuencia de ilustraciones va de izquierda a derecha y de arriba hacia abajo.

Comenzamos introduciendo a la cola C todos las aristas adyacentes al nodo inicial (el nodo 0). Luego, extraemos la arista 0-2 de la cola y procesamos las aristas adyacentes a 2, la 0-2 y la 2-6. No colocamos la arista 0-2 en la cola porque el vértice 0 ya fue visitado. Luego, extraemos la arista 0-5 de la cola y procesamos las aristas adyacentes a 5. De manera similar a la anterior, no se toma en cuenta la arista 0-5, pero si se encolan las aristas 5-3 y 5-4. Seguidamente, extraemos la arista 0-7 y encolamos la arista 7-1. La arista 7-4 está impresa en color gris porque si bien es un enlace adyacente a 7, podríamos evitar

encolarla debido a que ya existe una arista en la cola que nos lleva hasta el nodo 4.

Para completar el recorrido, tomamos las aristas que quedan en la cola, ignorando aquellas que están impresas en color gris cuando queden de primeras en la cola. Las aristas entran y salen de la cola en el orden de su distancia del vértice 0.

Al igual que en el DFS, usando el BFS se puede obtener un conjunto de aristas de cubrimiento mínimo del grafo, conocido como el árbol (BFS Tree).

También puede modificarse fácilmente y utilizarse para resolver problemas sencillos como los de conectividad simple, detección de ciclos y camino simple.

El BFS es el algoritmo clásico para encontrar el camino más corto entre dos nodos específicos en un grafo, mientras que DFS nos ofrece muy poca ayuda para esta tarea debido a que el orden en el que se visitan los nodos no tiene absolutamente ninguna relación con la longitud de los caminos.

...