Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2021/2022

6. Algoritmos fundamentales sobre grafos

Horas de clases presenciales: 14 (6 teoría + 8 prácticas)
Horas de trabajo no presencial: 28
Ratio: 4 horas no presenciales por cada clase de 2 horas

  1. Definición y representación
  2. Ordenación topológica y algoritmo de Kahn
  3. Búsqueda en anchura y camino óptimo sin pesos
  4. Camino óptimo con pesos y algoritmo de Dijkstra
  5. Árbol de recubrimiento óptimo y algoritmo de Prim
  6. Búsqueda en profundidad
  7. Componentes conexas y algoritmo de Kosaraju-Sharir

Recursos

El capítulo 9 "Graph Algorithms" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss contiene todo lo que vamos a estudiar en este tema y más. Complementa las clases de teoría estudiando los siguientes apartados:

Estas animaciones de David Galles te pueden ayudar a entender mejor los algoritmos:

Recursos en castellano y opcionales

En castellano puedes consultar lo mismo (aunque con un pseudocódigo basado en Pascal en vez de C++) en el capítulo 9 "Algoritmos de grafos" de la edición "Estructuras de datos y algoritmos" (1995) de M. A. Weiss (Addison-Wesley Iberoamericana), prestando atención a posibles erratas corregidas en ediciones posteriores (su definición de "ciclo" en el apartado de definiciones es incorrecta). Aunque es una edición antigua, es más completa que la de 2013 con Java y tiene el mismo contenido que la de 2014 con C++.

El capítulo 14 "Grafos y caminos" del libro "Estructuras de datos en Java" (2013) de M. A. Weiss solo incluye una parte de nuestro tema 6, pero te puede interesar para esos apartados:

  • 14.1 Definiciones
    • 14.1.1 Representación
  • 14.2 Problema del camino más corto no ponderado // Búsqueda en anchura
  • 14.3 Problema del camino más corto con ponderaciones positivas // Algoritmo de Dijkstra
  • 14.5 Problemas de caminos en grafos acíclicos
    • 14.5.1 Ordenación topológica // Algoritmo de Kahn

Ten en cuenta que en esa edición de 2013 falta parte de nuestro temario: el algoritmo de Prim, la búsqueda en profundidad, y el algoritmo de Kosaraju-Sharir. La edición de 1995 mencionada antes sí que incluye también eso.

Puedes encontrar explicaciones alternativas de los algoritmos de Prim y de Dijkstra en el capítulo 4 "The Greedy Approach" del libro "Foundations of Algorithms" (2015) de R. E. Neapolitan.

Consulta los siguientes materiales si quieres apreciar mejor el interés del tema en el desarrollo de videojuegos:

Estas transparencias de Kevin Wayne acompañan al libro "Algorithm design" de Jon Kleinberg y Éva Tardos y contienen ejemplos interesantes:

Búsqueda A* (opcional)

Aunque no forma parte del temario de esta asignatura (se estudia en la asignatura VJ1231) la estrategia de búsqueda A* se utiliza mucho en videojuegos y tiene mucho en común con el algoritmo de Dijkstra, como hemos visto en la última sesión de teoría. Si te interesa, puedes profundizar en el tema estudiando el capítulo 3 "Solving Problems by Searching" del libro "Artificial intelligence: a modern approach" (2014) de Stuart J. Rusell y Peter Norvig, fundamentalmente los siguientes apartados (que retoman y complementan temas tratados previamente en el curso):

  • 2 Example problems
  • 4.2 Uniform-cost search
  • 5.1 Greedy best-first search
  • 5.2 A* search: Minimizing the total estimated solution cost
  • 6 Heuristic functions

También te pueden interesar los siguientes materiales:

Ejercicios

Presentación

Dedicaremos a una selección de ejercicios de este tema las últimas 4 sesiones de laboratorio del curso. El resto debes completarlo en el tiempo de trabajo no presencial.

En muchos de los ejercicios vas a implementar algunos de los algoritmos estudiados en clase de teoría, modificándolos en ocasiones para resolver nuevos problemas. Para ello, deberás añadir nuevos métodos a una de las siguientes clases:

Cuando queramos trabajar con grafos dirigidos, utilizaremos la primera clase. Cuando queramos trabajar con grafos no dirigidos, utilizaremos la segunda clase.

La clase GrafoDirigido permite recorrer eficientemente tanto los arcos de salida (adyacentes) como los arcos de entrada (incidentes) de cualquier vértice, para que cada algoritmo pueda utilizar lo que necesite. Esas listas de adyacencia e incidencia se han implementado con listas simplemente enlazadas de arcos. Esa no es la única implementación posible, pero es con la que trabajaremos. Opcionalmente, puedes ver implementaciones alternativas, con listas de adyacencia e incidencia implementadas usando vectores, en la web del curso 2020/2021.

La clase GrafoNoDirigido se diferencia en que todos los arcos son tanto de entrada como de salida, y por ello hay una única lista de arcos asociada a cada vértice.

Las dos clases están preparadas para trabajar con grafos ponderados. En los ejercicios en los que eso no sea necesario, puedes ignorar los pesos de los arcos.

Seguiremos el convenio de numerar los vértices consecutivamente desde 0. En aplicaciones en las que los vértices representen, por ejemplo, ciudades o asignaturas, supondremos que previamente las ciudades o asignaturas se han numerado con ese convenio.

Ambas clases incluyen un constructor que lee grafos de fichero en un formato inspirado en el formato DIMACS (entender lo que hace ese constructor para leer el fichero no es materia de esta asignatura, pero puedes mirarlo opcionalmente si tienes curiosidad). Eso te permitirá crear fácilmente tu propia colección de grafos de prueba, imitando este ejemplo.gr. Cada línea que empieza con 'a' debe contener la información de un arco (origen, destino y peso, en ese orden). Origen y destino han de ser enteros no negativos. El peso de cada arco puede ser cualquier valor real. No es necesario que los arcos aparezcan en el fichero en ningún orden particular. Una línea que empieza con 'n' seguida de un entero positivo indica la cantidad de vértices. La línea que empieza con 'n' es opcional y permite representar grafos en los que el último vértice no forma parte de ningún arco o en los que no hay arcos. Si esa línea no aparece, la cantidad de vértices viene dada por el mayor de los vértices que aparezcan en los arcos, más uno. Las líneas que no empiezan con 'a' ni 'n' son ignoradas, y también es ignorado todo lo que aparezca tras los datos necesarios en esas líneas: eso permite añadir comentarios en el fichero. Se considerará que todos los arcos son dirigidos o que todos son no dirigidos dependiendo de la clase que hayas elegido. Si leemos el fichero ejemplo.gr con el constructor de la clase GrafoDirigido, se considerará que representa el grafo de la siguiente figura:

Ejemplo de grafo inicial dirigido

Si el mismo fichero lo leemos con el constructor de la clase GrafoNoDirigido, se considerará que representa el grafo de la siguiente figura:

Ejemplo de grafo inicial no dirigido

Cuando el grafo es dirigido, el orden en que aparecen origen y destino dentro de cada línea es relevante. Cuando es no dirigido, no lo es.

Fíjate en el código del método mostrar para ver un ejemplo de cómo recorrer vértices y arcos en cada clase: puedes consultarlo tantas veces como necesites. También puedes ver eso en el enunciado del ejercicio 1.

Con cada una de las dos clases se incluye un programa de prueba con una función main que de momento lo único que hace es leer un grafo de fichero y mostrar, para cada vértice, sus arcos. Para probar tu solución en cada ejercicio, puedes modificar como creas conveniente tanto la función main como el ejemplo de grafo. Además, la mayoría de los ejercicios incluyen al final un enlace "Probar la solucion" que lleva a una carpeta en la que puedes encontrar otros ejemplos con los que puedes probar tus soluciones.

Si trabajas con OnlineGDB, puedes utilizar el botón "New File" para añadir un nuevo fichero (una nueva pestaña), copiar en él el contenido de ejemplo.gr, y modificarlo como quieras. De ese modo, al ejecutar el programa lo encontrará y leerá su contenido. Recuerda que no puedes compilar un programa que tiene dos funciones main: elimina o sustituye la que pone OnlineGDB por defecto.

Cuando necesites trabajar con colas, pilas o colas de prioridad, puedes optar libremente entre utilizar tus propias implementaciones o utilizar los contenedores de la Standard Template Library (STL) de C++, como aprendiste en los temas anteriores (recordatorio: ejemplos C++).

Apartados 6.1, 6.2 y 6.3 (tras la primera clase de teoría)

  1. Análisis de coste temporal

    Clase de teoría TE1 11/11, TE2 16/11

    Sea G = (V, E) un grafo dirigido. Considera el siguiente fragmento de pseudocódigo:

    contador = 0
    para cada vértice v ∈ V:
       para cada arco (v, w) ∈ E que sale de ese v :
          contador = contador + 1
    	      

    La forma eficiente de implementar eso es utilizar una representación del grafo mediante listas de adyacencia. Puedes ver eso representado gráficamente en las animaciones de David Galles (por ejemplo, Breadth-First Search) eligiendo la opción Adjacency List Representation.

    Empleando la clase GrafoDirigido, quedaría:

    int contador = 0;
    for (int v = 0; v < vertices.size(); v++)
       for (Arco * arco = vertices[v].primerArcoDeSalida;
            arco != nullptr;
            arco = arco->siguiente)
          contador = contador + 1;
    	      

    Empleando la clase GrafoNoDirigido, quedaría:

    for (int v = 0; v < vertices.size(); v++)
       for (Arco * arco = vertices[v].primerArco;
            arco != nullptr;
            arco = arco->siguiente)
          contador = contador + 1;
    	      

    ¿Cuál es en ese caso el coste temporal de esos dos bucles anidados?

    1. O(|V| · |E|)
    2. O(|V|2)
    3. O(|V| + |E|)
    4. O(|V|)
    5. O(|E|)

    Solución

  2. Caminos óptimos sin pesos mediante búsqueda en anchura

    Clase de prácticas LA1 y LA3 18/11, LA2 y LA4 23/11

    1. Vas a realizar una implementación del algoritmo de cálculo de caminos óptimos sin pesos mediante búsqueda en anchura que hemos presentado en el apartado 6.3. En este ejercicio, no busques el algoritmo en Internet: escríbelo tú, sabiendo lo que tiene que hacer. La animación Breadth-First Search de David Galles te puede servir de ayuda.

      Añade a la clase GrafoDirigido un método público

      vector<int> arbolDeCaminosOptimosSinPesos(int) const;
      	      

      que reciba como argumento un entero s y devuelva como resultado un vector de enteros en el que, para cada vértice v distinto de s, la posición v contenga el vértice predecesor de v en el camino más corto (con menos arcos) desde s hasta v, como ilustra el vector Parent en la animación de David Galles. Si v no es alcanzable desde s, en la posición v devuelve un -1 para indicarlo; si v es s, indícalo con un -2.

      Los caminos más cortos desde un vértice hasta todos los demás forman un árbol, que queda representado en ese vector por el padre de cada vértice en el árbol.

      Por ejemplo, con este grafo ejemploInalcanzable.gr y origen 3 un resultado podría ser [2, 0, 3, -2, 1, 3, 7, 3, 7, -1].

      Ejemplo de grafo

      Ejemplo de arbol de caminos optimos sin pesos

      Solución

      Probar la solución

      Está solución ilustra también cómo trabajar con un booleano visitado asociado a cada vértice, que es como se suele presentar la búsqueda en anchura y es algo con lo que puedes contar para resolver otros ejercicios. No obstante, en este ejercicio nos lo podríamos ahorrar, puesto que un vértice está visitado si y solo si su padre no es -1.

      Ejemplo de error

    2. Supongamos que en un videojuego hay varios monstruos y un jugador. Cada monstruo está situado en un vértice de un grafo y el jugador está situado en otro vértice. El jugador se puede desplazar de vértice a vértice siguiendo los arcos. Tienes que encontrar el monstruo al que puede llegar el jugador atravesando la mínima cantidad de arcos. ¿Qué algoritmo puedes emplear? No se pide que lo implementes, solo que lo razones.

      Solución

  3. Alcanzabilidad y conectividad mediante búsqueda en anchura

    Clase de prácticas LA1 y LA3 18/11, LA2 y LA4 23/11

    En este ejercicio debes empezar diseñando los algoritmos, partiendo de algo que ya conoces (la búsqueda en anchura) y adaptándolo para resolver nuevos problemas sobre accesibilidad (también denominada alcanzabilidad) y conectividad.

    Añade a la clase GrafoDirigido los tres metodos que se piden a continuación.

    1. Implementa un método público que, dados un grafo dirigido G = (V, E) y un vértice s, empleando búsqueda en anchura, averigüe en tiempo O(|V| + |E|) si todos los vértices del grafo son alcanzables desde s (es decir, para cualquier vértice t existe al menos un camino de s a t). El resultado será de tipo booleano.

      bool todosAlcanzablesDesdeVertice(int) const;
      		  

      Puedes probarlo con ejemploAlcanzables.gr y TestTodosAlcanzablesDesdeVertice.cpp.

      Ejemplo de grafo

      Si el grafo fuese no dirigido, ¿cambiaría la solución? Piénsalo, no es necesario que lo implementes.

      Solución

      Probar la solución

    2. [Fuente: apartado 3.5 "Connectivity in Directed Graphs" del libro "Algorithm design" de Jon Kleinberg y Éva Tardos]

      Debes distinguir estos dos conceptos, relacionados pero diferentes:

      • Si un grafo es no dirigido y, para cualquier par de vértices s y t, existe al menos un camino de s a t, el grafo se denomina conexo.

      • Si un grafo es dirigido y, para cualquier par de vértices s y t, existe al menos un camino de s a t, el grafo se denomina fuertemente conexo.

      Para averiguar si un grafo no dirigido es conexo, basta con elegir un vértice s cualquiera y comprobar que todos los vértices son alcanzables desde s, aplicando una sola vez el algoritmo del apartado 3.a, con coste temporal O(|V| + |E|). Para averiguar si un grafo dirigido es fuertemente conexo, eso no es suficiente. Piénsalo, para cada tipo de grafo.

      Existe, no obstante, una forma simple, aunque no trivial, de averiguar si un grafo dirigido es fuertemente conexo en tiempo O(|V| + |E|): realizando solamente dos búsquedas en anchura. Intenta deducir cómo.

      Ayuda

      Solución (idea): mira las páginas 42 y 41 en estas transparencias "Graphs" de Kevin Wayne.

      Una vez entendida esa idea, impleméntala añadiendo a tu clase un método público

      bool esFuertementeConexo() const;
      		  

      que devuelva un booleano indicando si el grafo es fuertemente conexo.

      Comprueba que ejemploNoFuertementeConexo.gr no es fuertemente conexo, y que pasa a serlo si le añades un arco (8,0).

      Ejemplo de grafo

      Solución

      Probar la solución

    3. Supongamos que en un videojuego necesitas averiguar si un enemigo situado en un vértice t de un grafo dirigido es alcanzable por un jugador situado en un vértice s, es decir, si existe al menos un camino desde s hasta t. ¿Qué algoritmo emplearías? ¿Cuál sería su coste temporal y espacial?

      Impleméntalo, añadiendo el siguiente método público a la clase GrafoDirigido:

      bool esAlcanzable(int, int) const;
      		  

      Solución

      Probar la solución

  4. Clase de teoría TE2 16/11

    Aciclicidad y ordenación topológica mediante el algoritmo de Kahn

    En este ejercicio debes realizar una implementación del algoritmo de Kahn, que hemos presentado en el apartado 6.2 del tema, para encontrar una ordenación topológica (topological sort). La animación Topological Sort (Using Indegree array) de David Galles te puede servir de ayuda.

    Añade a la clase GrafoDirigido el siguiente método público:

    void mostrarOrdenTopologico() const;
    	      

    Si el grafo no es acíclico, detéctalo y termina lanzando una excepción que lo indique, sin haber mostrado una ordenación topológica incompleta en la salida estándar.

    Solución

    Probar la solución

  5. Tenemos un grafo no dirigido que representa el escenario en el que se desarrolla un videojuego. Cada vértice representan una isla. Cada arco representa un puente que une dos islas, que puede atravesarse en ambos sentidos. El grafo no es necesariamente conexo.

    Para cada vértice, tenemos un contador con la cantidad de enemigos presentes en esa isla.

    Añade a la clase GrafoNoDirigido un método público

    int contarEnemigosCercanos(int islaJugador,
                               int puentes,
                               const vector<int> & cantidadDeEnemigos) const;
    	      

    que reciba como argumentos el vértice (la isla) en que se encuentra el jugador, la cantidad de puentes máxima que puede utilizar cada uno de sus enemigos, y un vector que tiene, para cada isla, la cantidad de enemigos presentes en la isla i en la posición i. El método debe devolver la cantidad de enemigos que en ese momento podrían alcanzar al jugador atravesando a lo sumo esa cantidad de puentes, incluyendo los enemigos que ya están en la misma isla que el jugador. Analiza su coste temporal y espacial.

    Por ejemplo, con el siguiente grafo ejemploIslas.gr, si el jugador se encuenta en la isla 1, si la cantidad de puentes que puede utilizar cada enemigo es 2, y si la cantidad de enemigos presentes en cada isla coincide con el número de la isla, entonces el resultado es 1 + 5 + 6 + 7 + 8 + 10 = 37.

    Ejemplo de grafo islas

    Solución

    Probar la solución

  6. Si tuvieras que comprobar que un grafo dirigido es acíclico (es decir, no contiene ningún ciclo), ¿qué algoritmo de los que conoces por ahora podrías utilizar? Impleméntalo, añadiendo el siguiente método público a la clase GrafoDirigido:

    bool esAciclico() const;
    	      

    ¿Cuál es su coste temporal y espacial?

    Solución

  7. [Fuente: adaptación del ejercicio 9.52 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

    Tenemos un grafo dirigido acíclico en el que cada vértice representa una asignatura y cada arco (a, b) representa que es necesario finalizar la asignatura a antes de empezar la asignatura b. Los estudiantes pueden cursar simultáneamente tantas asignaturas como quieran con la única condición de respetar todas las restricciones representadas en ese grafo. Todas las asignaturas son anuales y se ofrecen todos los años.

    Diseña un algoritmo eficiente que, dado el grafo, calcule la mínima cantidad de años necesarios para completar todas las asignaturas. Haz que muestre también cuáles son las asignaturas a cursar cada año para conseguir eso. Analiza su coste temporal y espacial. Impleméntalo, añadiendo el siguiente método público a la clase GrafoDirigido:

    int minimaCantidadAnyos() const;
    	      

    Por ejemplo, con el grafo ejemplo.gr se obtiene este resultado (los pesos de los arcos puedes ignorarlos).

    Ejemplo - grafo inicial sin pesos

    Solución

    Probar la solución

  8. Supongamos que una determinada enfermedad muy virulenta se puede adquirir por contagio de persona a persona o por la picadura de un mosquito infectado. Tenemos un grafo no dirigido, no necesariamente conexo, en el que los vértices representan personas y un arco entre dos personas representa que si cualquiera de las dos adquiere la enfermedad entonces rápidamente se la contagiará a la otra.

    Por ejemplo, con el siguiente grafo ejemploPicaduras.gr, si un mosquito picase a 4, por esa sola picadura acabarían infectados 0, 1, 4 y 5.

    Ejemplo grafo ejercicio picaduras

    Diseña un algoritmo eficiente para averiguar cuál es la mínima cantidad de picaduras necesaria para que se infecten todas las personas. Por ejemplo, con el grafo anterior el resultado sería 3. Analiza su coste temporal y espacial. Impleméntalo añadiendo el siguiente método público a la clase GrafoNoDirigido:

    int contarPicaduras() const;
    	      

    Solución

    Probar la solución

Apartados 6.4 y 6.5 (tras la segunda clase de teoría)

  1. Clase de teoría TE1 18/11, TE2 23/11

    Utiliza el algoritmo de Dijkstra para obtener un árbol de caminos de mínimo peso desde el vértice origen d hasta todos los demás vértices en el siguiente grafo ponderado dirigido.

    Grafo dirigido ejercicio Dijkstra

    Solución

    1. Utiliza el algoritmo de Dijkstra para obtener un árbol de caminos de mínimo peso desde el vértice central 4 hasta todos los demás vértices en el siguiente grafo ponderado no dirigido. Puedes considerar que cada arco no dirigido representa dos arcos dirigidos, uno con cada orientación, con el mismo peso.

      Grafo no dirigido ejercicio Dijkstra

      Solución

    2. Utiliza el algoritmo de Prim para obtener un árbol de recubrimiento de mínimo peso en el grafo anterior. Escoge el vértice central 4 como vértice inicial. Compara el resultado con el del algoritmo de Dijkstra.

      Solución

  2. Caminos óptimos con pesos mediante el algoritmo de Dijkstra

    Clase de prácticas LA1 y LA3 25/11, LA2 y LA4 30/11

    Añade a la clase GrafoNodirigido un método público

    vector<int> arbolDeCaminosOptimosConPesos(int) const;
    	      

    que reciba como argumento un entero s y, suponiendo que no hay arcos de peso negativo, devuelva como resultado un vector de enteros en el que, para cada vértice v distinto de s, la posición v contenga el vértice predecesor de v en el camino de mínimo peso desde s hasta v. Si v no es alcanzable desde s, en la posición v devuelve un -1 para indicarlo; si v es s, indícalo con un -2. Es análogo a lo que se pedía en el ejercicio 2, con la diferencia de que ahora nos interesan los caminos de mínimo peso en vez de los caminos de mínima cantidad de arcos (por tanto, el algoritmo a aplicar es diferente).

    Para ello, implementa la versión del algoritmo de Dijkstra que puedes encontrar en el apartado "Using a priority queue" de la página "Dijkstra's algorithm" de la Wikipedia (ahí dist[v] hace el mismo papel que v.dist en el libro de M. A. Weiss y la flecha invertida denota asignación).

    El algoritmo de Dijkstra es aplicable tanto con grafos dirigidos como con grafos no dirigidos. En este ejercicio vamos a trabajar con grafos no dirigidos.

    Haz uso de esta clase: ColaDePrioridadDecrementable (incluye un ejemplo de uso).

    La animación Dijkstra Shortest Path de David Galles también te puede servir de ayuda.

    Puedes ver ejemplos de árbol de caminos de mínimo peso (shortest-paths tree) en la página 4 de las transparencias "Greedy Algorithms II" de Kevin Wayne y en las soluciones de los ejercicios 9 y 10.a.

    Si pruebas tu implementación con TestArbolDeCaminosOptimosConPesos.cpp y ejemplo10.gr, que es el grafo del ejercicio 10, debes obtener este resultado.

    Ayuda con C++

    Recuerda que, para trabajar con infinito, puedes incluir limits y usar numeric_limits<float>::infinity() (ejemplo_infinity.cpp).

    Solución

    Probar la solución

  3. Árbol de recubrimiento óptimo mediante el algoritmo de Prim

    Clase de prácticas LA1 y LA3 25/11, LA2 y LA4 30/11

    Añade a la clase GrafoNodirigido un método público

    vector<int> arbolDeRecubrimientoOptimo() const;
    	      

    que devuelva como resultado un vector de enteros en el que, para cada vértice v, la posición v contenga el vértice predecesor de v en un árbol de recubrimiento óptimo, suponiendo que el grafo es conexo.

    Para ello, implementa la versión del algoritmo de Prim que puedes encontrar en el apartado "Pseudocódigo del algoritmo" de la página "Algoritmo de Prim" de la Wikipedia. Donde pone distancia[u]=0, falta decir que u es un vértice cualquiera elegido como vértice origen, por ejemplo el 0.

    Haz uso de nuevo de esta clase: ColaDePrioridadDecrementable.

    Puedes partir de tu solución del ejercicio 11 y hacer en ella los cambios necesarios para convertir el algoritmo de Dijkstra en el algoritmo de Prim.

    La animación Prim Minimum Cost Spanning Tree de David Galles también te puede servir de ayuda.

    Puedes ver ejemplos de árbol de recubrimiento óptimo (minimum spanning tree, MST) en la página 31 de las transparencias "Greedy Algorithms II" de Kevin Wayne y en la solución del ejercicio 10.b.

    Si pruebas tu implementación con TestArbolDeRecubrimientoOptimo.cpp y ejemplo10.gr, que es de nuevo el grafo del ejercicio 10, debes obtener un resultado equivalente a TestArbolDeRecubrimientoOptimo.salida. No te conformes con eso, comprueba que funciona bien también con otros grafos, por ejemplo este grafo de la Wikipedia (ayuda: wikipediaPrim.gr, TestArbolDeRecubrimientoOptimo2.cpp, TestArbolDeRecubrimientoOptimo2.salida).

    ¿Cuáles son las diferencias entre la implementación del algoritmo de Prim (solución del ejercicio 12) y la implementación del ejercicio de Dijkstra (solución del ejercicio 11)?

    Solución

    Probar la solución

    Mira también las páginas 18 y 19 en estas transparencias sobre el Minimum Spanning Tree (MST) de Kevin Wayne (en el algoritmo de Prim, s es un vértice inicial cualquiera; faltaría insertar s con peso 0 en Q o hacer PQdeckey(s,0); "s.t" significa "such that"; lo importante son las enormes similitudes y la mínima diferencia entre los algoritmos de Prim y Dijkstra).

  4. Clase de teoría TE2 23/11, TE1 18/11 y 16/12

    Considera de nuevo la versión del algoritmo de Dijkstra que puedes encontrar en el apartado "Using a priority queue" de la página "Dijkstra's algorithm" de la Wikipedia.

    1. En el ejercicio 11 se te ha proporcionado la clase ColaDePrioridadDecrementable, en la que internamente se utiliza un vector no ordenado. Analiza el coste temporal del algoritmo de Dijkstra cuando se hace uso de esa implementación de la cola de prioridad.

    2. Analiza cuál sería el coste temporal del algoritmo de Dijkstra si la cola de prioridad se implementase empleando un montículo binario. Para ello, recuerda la solución del ejercicio 8 del tema 4.

    3. A la vista de los resultados anteriores, ¿para qué tipo de grafo es preferible utilizar un vector no ordenado en vez de un montículo binario, y viceversa?

    4. Un montículo de Fibonacci es una estructura de datos que permite implementar colas de prioridad con estos costes temporales:

      Coste en el peor caso Coste amortizado
      Insertar O(1) O(1)
      EliminarMínimo O(n) O(log n)
      DisminuirPrioridad O(n) O(1)

      Sin necesidad de conocer cómo funcionan los montículos de Fibonacci, teniendo en cuenta solamente esa tabla de costes, ¿cuál sería el coste temporal en el peor caso del algoritmo de Dijkstra si la cola de prioridad se implementase utilizando un montículo de Fibonacci?

    Solución:

  5. Clase de teoría TE2 23/11

    ¿En qué se diferenciaría el análisis de costes del ejercicio 13 si se tratase del algoritmo de Prim en vez del algoritmo de Dijkstra?

    Solución

  6. El ejercicio 7 del tema 5.3 lo podríamos resolver ahora aplicando el algoritmo de Dijkstra, ¿por qué? Compara el coste temporal de la solución obtenida en el tema 5.3 empleando Programación Dinámica con el coste temporal de aplicar el algoritmo de Dijkstra con montículos de Fibonacci que has obtenido en el ejercicio 13.

    Solución

  7. [Fuente: varios alumnos de cursos pasados querían resolver este problema en un videojuego que estaban desarrollando]

    Estamos trabajando con grafos dirigidos y ponderados que representan posibles desplazamientos en un juego. Cada arco (u, v) lleva asociado un peso no negativo que es la energía que consume el jugador al desplazarse del vértice u al v. Añade a la clase GrafoDirigido un método público

    vector<bool> destinosValidos(int s, float e) const;
    	      

    que reciba como argumento el vértice s en el que se encuentra el jugador y la energía total e que puede consumir. El resultado debe ser un vector en el que cada posición i tenga el valor true si, y solo si, existe algún camino desde el vértice s hasta el vértice i cuyo peso (suma de los pesos de sus arcos) sea menor o igual que e.

    Solución

    Probar la solución

  8. [Fuente: ejercicio 23.2-5 del libro "Introduction to Algorithms" (2009) de T. H. Cormen, Ch. E. Leiserson, R. L. Rivest y C. Stein]

    Queremos utilizar el algoritmo de Prim para encontrar el árbol de recubrimiento óptimo en un grafo G = (VE) ponderado, no dirigido y conexo, en un contexto en el que los pesos de los arcos son valores enteros, posiblemente repetidos, entre 1 y P, siendo P una constante que no depende de la talla del grafo (por ejemplo, 1000). Piensa cómo implementar la cola de prioridad de modo que, en ese contexto concreto, se mejore el coste temporal que se obtiene empleando en el algoritmo de Prim montículos de Fibonacci, y justifica que es así. Puedes consultar la tabla del ejercicio 13.

    Solución

    1. Tenemos un grafo dirigido y ponderado que representa las calles de una ciudad. El grafo no es necesariamente acíclico. Cuando sucede un accidente en un vértice, los servicios de emergencia deciden la cantidad de ambulancias n necesarias y a continuación es necesario localizar rápidamente las n ambulancias que pueden llegar en el mínimo tiempo posible al lugar del accidente. El peso de cada arco es el tiempo estimado que le costaría a una ambulancia moverse de un vértice a otro siguiendo ese arco.

      Para facilitar eso, para cada vértice v del grafo disponemos de un dato de tipo entero ambulancia[v]. Si en ese vértice hay una ambulancia, ese dato es el identificador de la ambulancia; en caso contrario, vale -1. No hay más de una ambulancia en el mismo vértice. Podría haber inicialmente una en el vértice del accidente.

      Diseña un algoritmo para resolver eficientemente ese problema, e impleméntalo añadiendo a la clase GrafoDirigido el siguiente método público:

      void mostrarAmbulancias(int, int, const vector<int> &) const;
      		  

      El primer argumento es el vértice destino, el segundo es la cantidad de ambulancias necesarias y el tercero es el vector ambulancia descrito antes. Ese método deberá mostrar en la salida estándar lo antes posible los identificadores de las n ambulancias requeridas. En caso de no localizar suficientes, deberá mostrar las que encuentre e indicar que no hay más.

      Solución

      Probar la solución

    2. Escribe otro algoritmo para resolver más eficientemente el mismo problema en el caso particular de que el peso de todos los arcos sea 10.

      Solución

      Probar la solución

  9. [Fuente: adaptación del ejercicio 9.10 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

    Al aplicar el algoritmo de Dijkstra para encontrar caminos óptimos, podría suceder que hubiese varios caminos igual de buenos. En ese caso, el algoritmo elegiría uno cualquiera de ellos.

    Modifíca la solución del ejercicio 11 para convertirla en un método que reciba como argumentos dos vértices s y t y devuelva como resultado la cantidad de caminos óptimos (caminos de mínimo peso) de s a t, suponiendo que no hay arcos de peso cero.

    int contarCaminosOptimos(int, int) const;
    	      

    Puedes probarlo con ejemploEmpates.gr: contarCaminosOptimos(4, 2) debe devolver 5.

    Grafo no dirigido ejercicio contar caminos

    Solución

    Probar la solución

Apartados 6.6 y 6.7 (tras la tercera clase de teoría)

  1. Componentes conexas

    Implementa de nuevo el método del ejercicio 8, utilizando esta vez búsqueda en profundidad en vez de búsqueda en anchura:

    int contarPicaduras() const;
    	      

    Analiza su coste temporal y compáralo con el de la solución del ejercicio 8.

    Solución

    Probar la solución

  2. Alcanzabilidad

    1. Resuelve de nuevo el ejercicio 3.c, empleando esta vez búsqueda en profundidad en vez de búsqueda en anchura.

      bool esAlcanzable(int, int) const;
      		  

      Solución

      Probar la solución

    2. Sea G = (VE) un grafo dirigido que representa el escenario de un videojuego en el que se sitúan varios ratones que deben alcanzar un queso. Para cada vértice u ∈ V tenemos un booleano raton[u] que indica si en ese vértice se encuentra un ratón. El queso se encuentra en un vértice q ∈ V. Cada arco dirigido (vw) ∈ E representa un movimiento válido que permite a los ratones desplazarse del vértice v al vértice w (el movimiento de w a v no tiene por qué ser válido; por eso el grafo es dirigido).

      Para que el juego esté bien configurado, para cada ratón debe existir en el grafo al menos un camino desde el ratón hasta el queso (sin importar si pasa por vértices ocupados por otros ratones).

      Diseña un algoritmo eficiente que verifique que se cumple eso y analiza su coste temporal.

      Añade a la clase GrafoDirigido el siguiente método público:

      bool quesoAlcanzablePorTodosLosRatones(int, const vector<bool> &) const;
      		  

      El primer argumento es el vértice en que se encuentra el queso y el segundo es el vector de booleanos que indica en qué vértices hay un ratón. El resultado debe ser un booleano, que valdrá cierto si y solo si el queso es alcanzable por todos los ratones.

      Solución

      Probar la solución

  3. Componentes fuertemente conexas mediante el algoritmo de Kosaraju-Sharir

    Clase de teoría TE1 25/11, TE2 30/11

    Aplica a este grafo el algoritmo de Kosaraju-Sharir para encontrar las componentes fuertemente conexas, siguiendo la explicación del apartado 9.6.5 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss, que es equivalente (piensa por qué) a ese apartado de la Wikipedia.

    Grafo ejercicio Kosaraju-Sharir

    Ayuda: Grafo invertido

  4. Dado un grafo dirigido, queremos asignar un color a cada vértice con la siguiente condición: para todo par de vértices u y v, si se puede ir desde u hasta v y desde v hasta u (utilizando uno o más arcos) entonces el color de u debe coincidir con el de v; en caso contrario, sus colores deben ser diferentes.

    Podemos utilizar valores enteros positivos para identificar los colores.

    Añade a la clase GrafoDirigido el siguiente método público:

    vector<int> colorearConectados() const;
    	      

    El resultado debe ser un vector de enteros que en la posición v tenga el color asignado al vértice v, para cada vértice v del grafo.

    Por ejemplo, con este grafo ejemploColorearConectados.gr

    Grafo dirigido ejercicio colorear conectados

    una solución es [1, 1, 2, 2, 1, 3, 2, 2]:

    Grafo dirigido ejercicio colorear conectados

    Solución

    Probar la solución

  5. Grafos bipartidos

    Tenemos un grafo no dirigido que representa el escenario en el que se desarrolla un videojuego. Cada vértice representan una isla. Cada arco representa un puente que une dos islas, que puede atravesarse en ambos sentidos. El grafo no es necesariamente conexo.

    En el juego participan dos equipos de jugadores. Para empezar el juego tenemos que asignar un equipo a cada isla consiguiendo que (i) cada isla pertenezca a un equipo y solo uno; (ii) no haya dos islas conectadas por un puente asignadas al mismo equipo. No se exige asignar la misma cantidad de islas a cada equipo.

    Diseña un algoritmo para resolver eficientemente ese problema, e impleméntalo añadiendo a la clase GrafoNoDirigido un método público

    vector<int> repartirIslas() const;
    	      

    que devuelva como resultado un vector en el que la posición v contenga el equipo asignado al vértice v, o lance una excepción si no existe solución. Analiza su coste temporal.

    Por ejemplo, con el siguiente grafo ejemploIslas.gr

    Ejemplo de grafo islas

    un resultado correcto sería [1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2], es decir, asignar las islas 0, 2, 6, 8 y 9 al equipo 1 y las restantes islas al equipo 2:

    Ejemplo de grafo islas coloreado

    Sin embargo, si añadiéramos un puente entre las islas 4 y 5, o entre las islas 8 y 2, no existiría ningún reparto válido.

    Solución

    Probar la solución

  6. [Fuente: apartado 9.6.4 "Directed Graphs", dentro del 9.6 "Applications of Depth-First Search", en el libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss, y en la antigua edición en castellano "Estructuras de datos y algoritmos" (1995)]

    Aciclicidad y ordenación topológica mediante búsqueda en profundidad

    Clase de prácticas LA1 y LA3 02/12, LA2 y LA4 14/12

    Es aconsejable que resuelvas el ejercicio 21.a antes de este.

    El objetivo de la tercera sesión de laboratorio es practicar con la búsqueda en profundidad y aprender cómo puede modificarse para resolver dos problemas de forma diferente (e igual de eficiente) a cómo vimos en el tema 6.2. No se trata, por tanto, de resolver el ejercicio empleando el algoritmo de Kahn. Se trata de diseñar e implementar algoritmos diferentes, basados en el orden en que se recorren los vértices en la búsqueda en profundidad.

    Supongamos que G es un grafo dirigido en el que los vértices representan pruebas a superar en un juego y la existencia de un arco dirigido de p a q indica que la prueba p debe superarse antes que la prueba q (no significa "inmediatamente antes").

    1. En primer lugar, los diseñadores del juego necesitan un algoritmo eficiente que verifique que el grafo es acíclico, es decir, que es posible superar todas las pruebas respetando todas las dependencias.

      Ya sabes cómo resolver ese problema empleando el algoritmo de Kahn (ejercicio 6). Diseña ahora un algoritmo para resolver el mismo problema con el mismo coste temporal empleando búsqueda en profundidad (sin dejar de recorrer los vértices en el orden en que lo hace la búsqueda en profundidad). Piensa, por ejemplo, cómo detectar el ciclo durante un recorrido en profundidad del siguiente grafo (ejemploCiclo.gr).

      Ejemplo de grafo con ciclo

      Implementa ese algoritmo, añadiendo a la clase GrafoDirigido el siguiente método público:

      bool esAciclico() const;
      		  

      que devuelva true si el grafo no contiene ningún ciclo, y false en caso contrario.

      Ayuda

      Solución

      Busca los cuatro errores

      Probar la solución

    2. Supongamos ahora que, sabiendo que el grafo es acíclico, para jugar necesitamos encontrar un orden válido de superación de las pruebas, es decir, una ordenación topológica.

      La búsqueda en profundidad también permite resolver ese problema de forma diferente al algoritmo de Kahn (ejercicio 4). Piensa cómo e impleméntalo en un método público

      void mostrarOrdenTopologico() const;
      		  

      que muestre en la salida estándar dicha ordenación.

      Ayuda

      Solución

      Probar la solución

Programación dinámica con grafos

  1. Caminos óptimos con pesos en grafos acíclicos mediante Programación Dinámica

    Clase de prácticas LA1 y LA3 16/12, LA2 y LA4 21/12

    Sea G=(VE) un grafo dirigido ponderado. Dados un vértice origen s y un vértice destino t, queremos encontrar un camino desde s hasta t cuyo peso (suma de los pesos de sus arcos) sea mínimo. Ya sabemos resolver ese problema empleando el algoritmo de Dijkstra si los pesos son no negativos. Vamos a ver una forma de resolverlo más eficientemente, empleando programación dinámica, cuando el grafo es acíclico (no importa si hay pesos negativos o no).

    Para cualquier vértice v ∈ V, sea pesoCaminoÓptimo(v) el peso mínimo para ir desde el vértice s hasta v. Podemos calcular recursivamente pesoCaminoÓptimo(v) así:

    • si v = s, entonces pesoCaminoÓptimo(v) vale 0;

    • si v ≠ s y no existe en E ningún arco (u,v) que entre a v, entonces pesoCaminoÓptimo(v) vale ∞;

    • en cualquier otro caso, pesoCaminoÓptimo(v) es el mínimo valor, entre los arcos (u,v) que entran a v, de pesoCaminoÓptimo(u) + pesoArco(u,v).

    Si el resultado es ∞, indica que v no es alcanzable desde s.

    Para entender mejor esa solución recursiva y el uso de programación dinámica en este problema, haz una traza con el siguiente grafo para encontrar el peso mínimo desde s = 1 hasta t = 8.

    Ejemplo de grafo inicial

    1. Una vez entendida la recursión anterior, añade a la clase GrafoDirigido un método público

      float pesoCaminoOptimo(int, int) const;
      		  

      que reciba como argumento dos vértices s y t y devuelva el peso mínimo para ir desde s hasta t.

      Hazlo utilizando una tabla de resultados para no repetir cálculos, como has aprendido en el tema 5.3. Ten en cuenta que, en general, los pesos de los arcos pueden ser negativos: eso impide utilizar, por ejemplo, -1 para indicar que el peso que nos piden no ha sido calculado previamente. Tampoco podemos utilizar para ello ∞ si ese valor representa que el vértice es inalcanzable desde el origen (volver a calcular eso podría ser ineficiente).

      Para probar la implementación, debes utilizar un grafo acíclico (piensa por qué). Si quieres probarla con el ejemplo de la figura anterior, se corresponde con este ejemplo.gr.

      Ayuda

      Solución

      Probar la solución

    2. Modifica la solución del apartado anterior para convertirla en un método público

      void mostrarCaminoOptimo(int, int) const;
      		  

      que muestre en la salida estándar tanto la secuencia de vértices que constituye un camino de peso mínimo desde s hasta t como el peso de dicho camino. Al igual que en el apartado anterior, puedes utilizar otro método auxiliar.

      Solución

      Probar la solución

      Probar traza

    3. Analiza el coste temporal de este algoritmo y compáralo con el algoritmo de Dijkstra.

      Solución

    4. Si quisiéramos implementar el algoritmo de forma iterativa, sin utilizar recursión, ¿en qué orden habría que recorrer los vértices para rellenar la tabla de resultados? ¿De menor a mayor? ¿De mayor a menor? ¿Otro?

      Solución

Opcionalmente, en las evaluaciones de cursos anteriores puedes encontrar más ejercicios de este tema si quieres seguir practicando.