Algoritmia - Modificación BFS/DFS

   
Vista:

Modificación BFS/DFS

Publicado por Alejandro (3 intervenciones) el 07/07/2013 13:30:24
Hola!

Tengo que diseñar un algoritmo a partir del BFS o DFS que haga lo siguiente:

Partiendo de un vértice s, comprobar si existe como mucho un camino simple (no se repiten vértices en el camino) de s a cualquier otro vértice del grafo. El algoritmo tiene que ser O(|V|+|E|).

Y después a partir del anterior algoritmo, modificarlo para que compruebe lo mismo (que haya como mucho 1 camino simple) entre u y v. Este algoritmo debe ser O(|V||E|).

Muchísimas gracias de antemano! Espero que me podáis ayudar! :)
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
información
Otras secciones de LWP con contenido de Algoritmia
- Cursos de Algoritmia
- Temas de Algoritmia
- Chat de Algoritmia
información
Cursos y Temas de Algoritmia
- Recursividad
- Colas
- El algoritmo CORDIC

Modificación BFS/DFS

Publicado por Arturo gustavo@cbc.co.cu (4 intervenciones) el 12/01/2014 20:24:05
Lo primero lo haces efectuando un simple bfs sobre el grafo y todos los vértices que entren en la cola los marcas como vértices a los cuales existe un camino simple. (esto también lo puedes hacer con un dfs).
Lo segundo se resuelve de la siguiente forma:
haces una matriz de |V|x|V| y luego por cada vértice aplicas el primer algoritmo. El resultado lo pones en la fila correspondiente al vértice que estes analizando. Finalmente en la matriz quedara en la posición u,v si existe un camino simple entre u y v. Lo interesante aquí es el costo temporal. Es O(|V|+|E|) pues tenemos O(|V|*(V|+|E|))=O(|V|**2+|V|*|E|)=O(max(|V|**2,|V|*|E|))=O(|V|*|E|)
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar