elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Introducción a Git (Primera Parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Diferentes caminos entre dos nodos en un grafo
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Diferentes caminos entre dos nodos en un grafo  (Leído 9,444 veces)
dark_headhunter

Desconectado Desconectado

Mensajes: 208


solo tu eres dueño de tu destino


Ver Perfil WWW
Diferentes caminos entre dos nodos en un grafo
« 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
  {
    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:
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.


En línea

La informacion es nuestra arma, el anonimato nuestra armadura
pucheto

Desconectado Desconectado

Mensajes: 215


Ver Perfil
Re: Diferentes caminos entre dos nodos en un grafo
« Respuesta #1 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)).


« Última modificación: 14 Julio 2011, 05:02 am por pucheto » En línea

pucheto

Desconectado Desconectado

Mensajes: 215


Ver Perfil
Re: Diferentes caminos entre dos nodos en un grafo
« Respuesta #2 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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Medir el ancho de banda entre dos nodos en una LAN
Redes
madpitbull_99 2 12,833 Último mensaje 3 Agosto 2011, 01:50 am
por Kasswed
Como Crear un Grafo en SvG?
Programación C/C++
gasparenaide 0 2,300 Último mensaje 9 Abril 2013, 06:10 am
por gasparenaide
todos los caminos de un grafo
Java
bengy 1 2,717 Último mensaje 11 Junio 2014, 03:47 am
por Gh057
Duda con Algoritmo para ver todos los caminos de longitud r entre cada ...
Programación General
peterk07 1 2,137 Último mensaje 6 Julio 2014, 06:32 am
por El Benjo
Grafos: camino mas corto entre dos nodos[c++]
Programación C/C++
KINGARZA 2 3,154 Último mensaje 9 Noviembre 2016, 20:38 pm
por KINGARZA
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines