Título: Diferentes caminos entre dos nodos en un grafo Publicado por: dark_headhunter en 13 Julio 2011, 06:25 am Hola amigos, estoy realmente atascado y vengo a por ayuda :)
Tengo un grafo con la siguiente estructura de datos (C#) : Código: public class Grafo El tema es que tengo que sacar que nodos con comunes a todas las rutas diferentes entre dos nodos dados. La idea está clara, calcular todas las rutas posibles, y ver que nodos son comunes a todas. Mi problema viene que no tengo claro como pasarlo a codigo. He pensado hacer recorridos en profundidad, donde cada no nodo visitado se añade a una lista de recorridos ya hechos y si llega al punto final, se devuelve ese conjunto. Con todos los conjunto ya solo sería ver si que nodos se repiten en las combinaciones resultantes. De momento llevo esto: Código: public int process(int A, int B) Gracias de antemano. Título: Re: Diferentes caminos entre dos nodos en un grafo Publicado por: pucheto en 14 Julio 2011, 03:46 am A ver si entendi, vos lo que queres, es encontrar un punto q sea comun a todos los caminos entre el nodo v_1 y v_2.
Calcular todas las rutas posibles y ver q nodos son comunes es una locura. Ver todos los caminos puede llegar a tener complejidad exponencial. Lo que vos queres buscar seria algo asi como puntos de quiebre en el grafo. Tal que si sacas el nodo, te quedan 2 o mas componentes conexas separadas, y v_1 pertenece a una componente distinta de la de v_2. Habia un algoritmo para esto, ahora busco y si lo encuentro aviso. PD: Rapido, facil, y a lo bruto, uno puede sacar cada nodo, y hacer un bfs para ver si hay un camino entre v_1 y v_2... ponele, en un grafo muy ortiva, completo tendrias complejidad O(n*(n+m)). Título: Re: Diferentes caminos entre dos nodos en un grafo Publicado por: pucheto en 14 Julio 2011, 05:01 am Tiro dato, el problema se puede resolver en O(n + m).
* Primero armo un arbol para ver si el grafo es biconexo (pagina 439 del Algorithms in C de Schedwik o algo asi). * Veo cuales de estos nodos son puntos de 'articulacion' * Hago un BFS para conseguir el camino minimo entre v_1 y v_2. * Usando este camino, veo cuales de estos puntos son de articulacion. Si un punto esta en el camino y es de articulacion, lo agregas al conjunto resultado. |