# Árbol Abarcador de un Grafo _© F.J. Madrid Cuevas () Estructuras de Datos. Grado de Ingeniería Informática. Universidad de Córdoba. España_ ## Objetivo - Aprender a implementar el TAD Grafo usando una matriz adyacencia. - Implementar los algoritmos para obtener el árbol abarcador en profundidad y en anchura de un grafo. - Implementar un algoritmo para realizar la ordenación topológico de un grafo dirigido acíclico. - Implementar el algoritmo de Prim para obtener el árbol abarcador de coste mínimo. - Implementar el algoritmo de Kruskal para obtener el árbol abarcador de coste mínimo. - Conocer y aprender a utilizar el TAD Disjoint-Set. - Implementar una función de comparación personaliza para el algoritmo std::sort. ## Descripción En esta práctica vamos a obtener árboles abarcadores de un grafo. Un árbol abarcador de un grafo, es un subgrafo conexo sin ciclos. Si el grafo no es conexo, obtendremos varios árboles abarcadores, uno para cada componente conexa del grafo. ### Árboles abarcadores en profundidad o en amplitud De forma genérica podemos procesar un grafo siguiendo un esquema de “primero en profundidad” o “primero en amplitud”. En el procesado en profundidad, usaremos un esquema recursivo con procesado prefijo de los vértices. En el procesado en amplitud, usaremos un esquema iterativo usando una cola para realizar un procesado prefijo de los vértices. ### Ordenación topológica de un grafo dirigido acíclico Es una especialización de árbol abarcador en profundidad aplicado a un grafo dirigido acíclico donde el lado dirigido “u->v” significa: “u” es un prerrequisito para “v”. En este caso el procesado de los vértices es postfijo y el resultado es una lista de vértices donde si “u” es un prerrequisito para “v”, el vértice “u” aparecerá antes que “v” en la lista. ### Árbol abarcador de coste mínimo Se aplican en grafos ponderados y es, de todos los posibles árboles abarcadores, aquel cuya suma de pesos de los lados seleccionados sea la mínima posible (pueden existir varias soluciones todas con el mismo coste mínimo). Para obtener el árbol abarcador de coste mínimo vamos a implementar los algoritmos de Prim y Kruskal y comparar sus salidas. #### Algoritmo de Prim La implementación del algoritmo de Prim es directa a partir de la descripción que hemos visto en clase. Recuerda que vamos a necesitar usar una cola de prioriad. Para ello debemos implementar el TAD Heap. Opcionalmente (obteniendo menos nota) podrás usar el tipo `std::priority_queue` de la STL de C++. #### Algoritmo de Kruskal Para implementar el algoritmo de Kruskal vamos a utilizar un TAD auxiliar para “colorear” los vértices del grafo. Este TAD es conocido como “Disjoint Set.” [1].
```pascal ADT DisjointSets Makers: DisjointSets(capacity:Integer) //Create with at most capacity disjoint sets. Observers: capacity():Integer //Get the maximum number of disjoints sets. isSet(i:Integer):Bool // Is i in a disjoint set? pre-c: 0 <= i < capacity() find(i:Integer):Integer //Find the set for the element i. pre-c: isSet(i) post-c: retV=-1 or find(retV)=retV Modifiers: makeSet(i:Integer) // make a new disjoint set for the element i. pre-c: 0 <= i < capacity() post-c: find(i)=i joint(i,j:Integer) // joint the disjoint sets of the elements i and j. pre-c: isSet(i) pre-c: isSet(j) post-c: find(i) = find(j) ``` **Figure 1**: Especificación del TAD DisjointSets.
Supongamos que `ds` es un valor del TAD `DisjointSets` con tamaño el número de vértices del grafo. Inicialmente cada vértice tiene un “color” distinto (pertenece a un conjunto cuyo único elemento es ese vértice). Esto se hace con `ds.make_set(v.label())` para todo vértice `v` del grafo. Después, durante el algoritmo, al seleccionar un lado que conecta dos vértices `u`, `v`, podemos usar la interfaz `ds.find(u.label())` para saber el “color” del vértice `u` y `ds.find(v.label())` para saber el “color” de `v`. Si sus colores son iguales, ese lado no nos interesará, pero si son distintos, ese lado lo añadiremos al árbol abarcador y además deberemos unir los conjuntos disjuntos para formar uno solo conjunto con la interfaz `ds.join(u.label(), v.label())`. Al final del algoritmo, todos los vértices deberían tener el mismo color (pertenecer al mismo conjunto) ya que como precondición el grafo debe ser conexo. En caso contrario es una violación de la precondición porque el grafo no es conexo. Por otra parte, para ordenar la lista de lados, vamos a utilizar el algoritmo std::sort al que le daremos un functional (en [2] tienes un ejemplo) para que compare dos lados de forma aplicando "orden lexicográfico" asumiendo que un lado $(u, v)$ con peso $w$ lo vamos a representar por la tupla `(w, u, v)`. Es interesante que compruebes que aunque se pueden obtener soluciones diferentes con Prim (usando distintos nodos origen) y Kruskal, todas deben tener el mismo coste mínimo. ## Evaluación Ver fichero `TESTS.json` para ver los tests y su peso en la evaluación. Se recomienda la siguiente forma de realizar la práctica: - **Primera semana**: tests de WGraph recorridos en profundidad y amplitud. - **Segunda semana**: tests de algoritmos de ordenación topológica, Prim y Kruskal. \* **Nota**: si el TAD Grafo ya hubiera sido implementado en otra práctica sólo se evaluarán los tests relativos a los árboles abarcadores escalando la puntuación [0, 5] al rango [0, 10]. ## Plan de entregas Ver fichero `DATES.json` para ver las fechas de entrega. ## Referencias [1] [https://en.wikipedia.org/wiki/Disjoint-set_data_structure]. [2] [http://www.cplusplus.com/reference/algorithm/sort/].