Diferentes caminos entre dos nodos en un grafo

[dark_headhunter]

Hola amigos, estoy realmente atascado y vengo a por ayuda

Tengo un grafo con la siguiente estructura de datos (C#) :

Código [Seleccionar] Expandir

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:

Código [Seleccionar] Expandir

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.

[pucheto]

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)).

[pucheto]

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.