Hola amigos, estoy realmente atascado y vengo a por ayuda :)
Tengo un grafo con la siguiente estructura de datos (C#) :
public class Grafo
{
int count = 0;
Dictionary<int, string> nombrevertices;
Dictionary<int, Object> vertices;
Dictionary<int, ArrayList> adjacencias;
bool [] visitados;
string[] acum;
public Grafo()
{
vertices = new Dictionary<int, Object>();
adjacencias = new Dictionary<int, ArrayList>();
nombrevertices = new Dictionary<int, string>();
}}
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:
public int process(int A, int B)
{
visitados = new bool[ObterNumVertices()];
acum = new string[ObterNumVertices()];
return 0 ;
}
public int process2(int A, bool [] V)
{
V[A] = true;
int i;
int[] adj = new int[(ObterNumVertices())];
acum[A] = (string)(acum + nombrevertices[A]);
adj(ArrayList) = adjacencias[A];
for (i = 0; i < adjacencias.Count;i++ )
{
if (!V[i])
{
//process2((int)adjacencias[A][i],V);
}
}
return 0;
}
No sé ni bien como acceder a la de adyacencias en process2 y tengo un cacao enorme en la cabeza. ¿Podéis ayudarme?
Gracias de antemano.
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)).
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.