Tarea #7 [solución]

Camino en un grafo dirigido

      Un Grafo G(V,A) tiene 2 componentes principales: V, que es un conjunto de vértices, y A, el conjunto de arcos o aristas, que es un conjunto de enlaces entre los vértices (en este caso, los enlaces sí tienen dirección). Si los valores de los arcos son números y los vértices son hileras, una manera de representar el grafo es utilizar una tabla como la siguiente:

Fuente->Base(1) == 12   Medio->Fin(1) == 13   Fuera->Adentro == 13
Fuente->Medio   ==  6   Medio->Fin(2) == 23   Adentro->Fuera == 13
Fuente->Base(3) == -3   Medio->Fin(3) == -7
                    
Base(1)->Medio == -3    Fin(1)->Destino == 1
Base(2)->Medio == 10    Fin(2)->Destino == 0
Base(3)->Medio == 20    Fin(3)->Destino == 1

          Base(1)             Fin(1)
         /       \           /      \
        /         \         /        \
Fuente---------------Medio----Fin(2)---Destino   Fuera -- Adentro
        \         /         \        /
         \       /           \      /
          Base(3)             Fin(3)

      Para implementar el grafo use un diccionario std::map<> en que la llave sea una hilera (pues los vértices son hileras), y el como valor asociado use lista que almacene parejas de valores, en donde esté la hilera que identifica que identifica al vértice de destino, junto con el valor numérico asociado al vértice.

      El método booleano conectado() del grafo retorna "true" si existe una secuencia de aristas que permiten ir desde un vértice hasta otro. Además, conectado() también calcula y retorna la lista de nodos que hay que visitar para llegar de un nodo a otro. Por ejemplo, conectado() debe producir la lista ( "Base(1)" , "Medio" , "Fin(2)" ) que es el camino de ir desde "Base(1)" hasta "Fin(2)" a un costo de 20==(-3+23).

      Entregue su tarea por correo electrónico, como lo hizo anteriormente.

Entrega de Tareas

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2007
Derechos de autor reservados © 2007