NIVEL 17: ESTRUCTURAS NO LINEALES · Clase Vértice •Problema: ¿Cómo retornar el camino de...

ISIS1206 – Estructuras de Datos

http://cupi2.uniandes.edu.co

NIVEL 17: ESTRUCTURAS NO LINEALES

Búsqueda caminos y ciclos

Agenda

• Caminos en un grafo

• Caminos acíclicos• Caminos con ciclos

• Clase Camino

• Camino entre dos vértices

• Camino más barato entre dos vértices y su costo

• Detección de ciclos

• ¿Hay ciclos desde un vértice?

• ¿El grafo es acíclico?

Caminos en un grafo acíclico

• ¿Cómo buscar caminos en un grafo dirigido utilizando un planteamiento recursivo?

Verificación de existencia:• Problema: Determinar si existe un camino entre dos vértices v1 y v2 de un grafo

Grafo acíclico Grafo con ciclos

Verificación de existencia:• Problema: Determinar si existe un camino entre dos vértices v1 y v2 de un grafo.

Grafo acíclico: No hay riesgo de quedarse haciendo llamadas recursivas.

Se trata como si fuera un árbol n-ario.

Grafo con ciclos

Verificación de existencia:• Problema: Determinar si existe un camino entre dos vértices v1 y v2 de un grafo

Grafo acíclico Grafo con ciclos: Los ciclos pueden generar llamadas recursivas infinitas.

Es necesario recordar los puntos por los cuales ya ha pasado el proceso de búsqueda para evitar hacer de nuevo una llamada recursiva desde ese vértice.

MARCAR

Formalismo extendido para incluir la noción de vértice marcado

• G = ( V, A, V’ ), V’ V, v V’ si v está marcado

v5Marcados

Caminos en un grafo acíclicoVerificación de existencia:

• Problema: Determinar si existe un camino entre dos vértices v1 y v2 de un grafo acíclico

Grafo acíclico: No hay riesgo de quedarse haciendo llamadas recursivas

Se trata como si fuera un árbol n-ario

• Verificar si existe un camino a un vértice destino en un grafo acíclico (clase Vértice)

• Salida de la recursión: cuando el vértice actual (origen) coincide con el vértice destino

• Recorre los arcos a sus sucesores

• Obtiene el vértice sucesor

• Verifica si hay camino desde el vértice sucesor hasta el destino final

Caminos en un grafo acíclico• Verificar si existe un camino a un vértice destino en un grafo

acíclico (clase Vértice)

• Después de haber recorrido todos los sucesores retorna falseindicando que no encontró el camino

Agenda

• Caminos acíclicos

• Caminos con ciclos

• Clase Camino

Caminos en un grafo con ciclos

• ¿Y si hay ciclos ?

• ¿Hay camino entre V3 y V2 ?

• ¿V3.hayCaminoEnAciclico(v2) ?

• RECURSIÓN INFINITA

Caminos en un grafo con ciclos• ¿Hay camino entre V3 y V2 ?

• SOLUCIÓN: MARCAR

• Cuando pase por v3 se marca, de forma tal que la siguientevez que se vaya a pasar por ahí, se ignora porque el vérticeya fue visitado

Caminos en un grafo con ciclos• Verificar si existe un camino a un vértice destino en un grafo con ciclos

(clase Vértice)

• Misma salida de la recursión: cuando el vértice actual (origen) coincide con el vértice destino

(clase Vértice)

• Marca el vértice para recordar que ya pasó por ahí

(clase Vértice)

• Recorre los arcos a sus sucesores

• Verificar si existe un camino a un vértice destino en un grafo con ciclos (clase Vértice)

Caminos en un grafo con ciclos• Verificar si existe un camino a un vértice destino en un grafo con

ciclos (clase Vértice)

1. Que el vértice sucesor no haya sido visitado previamente

2. Que haya camino desde el vértice sucesor hasta el destino final

• Nuevos métodos en la clase Vértice para manejar las marcas

Agenda

• Clase Camino

Retornar el camino

• Problema: Determinar si existe un camino entre dos vértices v1 y v2 de un grafo y retornarlo.

• Nueva clase en Cupi2Collections para representar y manipular Caminos

Clase Camino

• El vértice origen del camino es de tipo Vertice

Clase Camino• Se declara un vector (arcos) que contiene los arcos del camino

Clase Camino• Se declara el costo del camino

Clase Camino• Se crea el camino a partir de un vértice origen

Clase Camino

• Métodos empleados:• public Camino( Vertice<K, V, A> pOrigen )

• public void agregarArcoFinal( Arco<K, V, A> arco )

• public void agregarArcoComienzo( Arco<K, V, A>

nuevoArco )

• public void concatenar( Camino<K, V, A> camino )

• public void eliminarUltimoArco( )

• public void reiniciar( )

• public int darLongitud( )

• public int darCosto( )

• public Iterador<Vertice<K, V, A>>

darSecuenciaVertices( )

Agenda

• Clase Camino

Camino entre dos vértices (Clase Vértice)• Retornar un camino a un vértice destino

• Se retorna un objeto de tipo camino

• Si es el vértice buscado retorna un camino nuevo con el vértice origen (sin arcos)

• Marca el vértice para recordar que ya pasó por ahí.

• Recorre los arcos sucesores

• Verifica que el vértice sucesor no haya sido visitado previamente

• Obtiene el camino desde el sucesor hasta el destino

• Si encontró algún camino del sucesor al destino (!= null), adiciona el arco al inicio de la lista de arcos del camino y retorna el camino

• Si al haber recorrido todos sus sucesores no encontró camino al destino retorna null

Agenda

• Clase Camino

Clase Vértice• Problema: ¿Cómo retornar el camino de costo mínimo entre dos vértices v1 y v2 de un grafo dirigido que puede tener ciclos?

• Parecido al problema anterior (darCamino), pero debe buscar TODOS los caminos posibles entre los dos vértices antes de retornar el camino (para estar seguro de retornar el de costo mínimo).

Qué pasa si usamos el dar Camino original ?

Camino de costo mínimo de v1 a v4 ?

Primer camino que encuentra: < v1, v2, v4> con costo 12. No es el de

menor costo !!!

Qué modificaciones hay que hacer?

1. Encontrar TODOS los caminos (junto con su costo) de v1 a v4 para seleccionar el menor.

• Obliga a hacer una llamada recursiva a cada sucesor no marcado y según el costo que retorne cada llamada, seleccionar el mejor.

2. Desmarcar el nodo v1 antes de abandonar el método:

• Es indispensable porque se puede dar el caso de que el camino buscado pase por el nodo v1, pero viniendo de otra llamada recursiva

Qué pasa si no se desmarca ?

Camino de costo mínimo de v1 a v4 ?

•Después de la primera recursión, v2 queda marcado.•Al buscar los caminos desde v1 que comiencen por v3, solo va a encontrar el camino <v1, v3, v4> , ignorando el camino de costo mínimo < v1, v3, v2, v4 > porque v2 estaba marcado.

Qué pasa si no se desmarca ?

•Después de la primera recursión, v2 queda marcado.•Al buscar los caminos desde v1 que comiencen por v3, solo va a encontrar el camino <v1, v3, v4> , ignorando el camino de costo mínimo < v1, v3, v2, v4 > porque v2 estaba marcado.

Es necesario desmarcar los nodos en todos los algoritmos que deban

identificar todos los posibles caminos entre dos puntos

Retornar el camino de costo mínimo a un vértice destino (clase Grafo)

• Complete el siguiente método

* Retorna el camino más barato (de menor costo) entre el par

* de vértices especificados

* @param idVerticeOrigen Vértice en el que inicia el camino

* @param idVerticeDestino Vértice en el que termina el camino

* @return El camino más barato entre el par de vértices

* especificados

* @throws VerticeNoExisteException Si alguno de los dos

* vértices no existe

public Camino darCaminoMasBarato( K idVerticeOrigen, K

idVerticeDestino ) throws VerticeNoExisteException {

// Borra todas las marcas presentes en el grafo

// Obtiene los vértices

// Le pide al vértice de origen que localice el camino

Retornar el camino de costo mínimo a un vértice destino (clase Grafo)

* Retorna el camino más barato (de menor costo) entre el par

* de vértices especificados

* @param idVerticeOrigen Vértice en el que inicia el camino

* @param idVerticeDestino Vértice en el que termina el camino

* @return El camino más barato entre el par de vértices

* especificados

* @throws VerticeNoExisteException Si alguno de los dos

* vértices no existe

public Camino darCaminoMasBarato( K idVerticeOrigen, K

idVerticeDestino ) throws VerticeNoExisteException {

// Borra todas las marcas presentes en el grafo

reiniciarMarcas();

// Obtiene los vértices

Vertice<K, V, A> verticeOrigen = darVertice( idVerticeOrigen );

Vertice<K, V, A> verticeDestino = darVertice( idVerticeDestino );

// Le pide al vértice de origen que localice el camino

return verticeOrigen.darCaminoMasBarato( verticeDestino );

Camino más corto (clase Vértice)

• Implemente el siguiente método

* Devuelve el camino mas corto al vértice especificado

* @param destino Vértice destino

* @return Camino mas corto hacia el vértice especificado

public Camino<K, V, A> darCaminoMasCorto( Vertice<K, V, A> destino )

//Si el origen y destino son iguales retorne un camino con el

//vértice actual

//De lo contrario:

//Marque el vértice actual

//Pida los arcos sucesores

//Recorra los sucesores

//Por cada arco obtenga el vértice y si no esta marcado llame la

//recursión.

//Si el camino anterior existe y (no ha encontrado el camino más corto o

//la longitud del camino actual es menor que la longitud del camino más

//corto que llevaba -> Actualice el camino mas corto y el arco.

//Después de recorrer todos los arcos desmarque

//Si el camino no existe retorne null

//Si el camino existe agregue el arco al camino y retórnelo

Clase Vértice• Retornar el camino con menor costo a un vértice destino

• Se declaran variables auxiliares donde se guarda la información del último hasta el momento

• Se hace el mismo ciclo anterior verificando que el vértice sucesor no esté marcado

• Se calcula recursivamente el camino más barato desde el sucesor hasta el destino

• Se verifica que el vértice sucesor encuentre su propio camino más barato

• Se calcula el costo de ese camino, incluyendo el arco al nodo sucesor

• Si el nuevo costo es menor que el menor hasta el momento (o si es la primera vez), se actualizan los valores de las variables auxiliares.

• Después de haber recorrido TODOS los vértices sucesores:

• Se desmarca

• Verifica si encontró camino mínimo. En este caso, añade el arco que lleva al vértice origen de ese camino

Agenda

• Clase Camino

• Detección de ciclos• ¿Hay ciclos desde un vértice?

¿Hay un ciclo desde un vértice?

• Implementar el siguiente método:

• ¿En qué clase va este método ?

Ayuda: Utilice el método hayCamino( )

¿Hay un ciclo desde un vértice?

• Implementar el siguiente método:

• ¿En qué clase va este método ?

Agenda

• Clase Camino

¿El grafo es acíclico ?

• Implementar un método que diga si el grafo es acíclico.

• En qué clase va este método ?

Ayuda: Utilice el método hayCamino( )

NIVEL 17: ESTRUCTURAS NO LINEALES · Clase Vértice •Problema: ¿Cómo retornar el camino de...

Documents

Transcript of NIVEL 17: ESTRUCTURAS NO LINEALES · Clase Vértice •Problema: ¿Cómo retornar el camino de...

Tema 5 Grafos.. Grafos Un grafo se define como un par G = (V, A), donde V es un conjunto finito no vacío de vértices A es un conjunto de pares de vértices.

Matemáticas discretas, aplicaciones y ejercicioseditorialpatria.com.mx/pdffiles/9786074387384.pdf · Grafo regular ... Grafo aplanable .....218 Región de un grafo aplanable .....218

Teoría de grafos - estructuradatos.tripod.comestructuradatos.tripod.com/temas/tema9.pdf · Teoría de grafos Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y ciencias

2 Autómatas finitos y gramáticas regulares.mtovar/doc/LFAA/Unidad2AFDC.pdf · Estado Finito es un grafo en el que los vértices representan los distintos estados y los arcos las

Sesión de grafo motricidad

Técnicas Grafo plásticas

Grafos parte 2mtovar/doc/MatDisc/GrafosParte2b.pdf · Un grafo no dirigido es conectado si existe una ruta entre cada par de distintos vértices del grafo. Un grafo no dirigido no

En busca del grafo

CADENAS DE MARKOV EN TIEMPO DISCRETOestadistica.net/INVESTIGACION/Markov-discreto.pdf · vértices del grafo dirigido y pij es el inverso del número de aristas salientes desde i

Grafo Facebook Digicom

“GRAFOS” - fcaenlinea1.unam.mxfcaenlinea1.unam.mx/anexos/1566/1566_u4_anexo3.pdf · GRAFOS Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos.

Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,

Tema: Grafos en C# · Matriz de adyacencia. El grafo se representa por una matriz de tamaño VxV, donde V son los vértices que unen a los nodos, la conjunción de los dos vértices

Tipos de grafos - cs.buap.mxmtovar/doc/MatDisc/grafosParte2Simple.pdf · Complemento de un grafo (G’) 9/29/2015 13 Grafo G Grafo Complemento G’ Es el grafo que le falta al grafo

Estructuras de datos y algoritmos · 4.1 Grafos Un grafo es una estructura de datos que almacena datos de dos tipos: • vértices o nudos, con un valor almacenado • aristas o arcos:

Proyecto grafo

lados y vértices

MIGRAR, MORIR , ¿RETORNAR

Grafo Inicial

grafo componentes