¿Cómo determinar si dos nodos están conectados?

votos
13

Me preocupa que esto pueda estar funcionando en un problema NP-Completo. Espero que alguien me pueda dar una respuesta si es o no. Y estoy buscando más respuestas que solo sí o no. Me gustaría saber por qué. Si puede decir: Esto es básicamente este problema 'x' que es / no es NP-Complete. (Enlace de wikipedia)

(No, esto no es tarea)

¿Hay alguna manera de determinar si dos puntos están conectados en un gráfico arbitrario no dirigido? por ejemplo, el siguiente

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

Los puntos A a M (sin 'I') son puntos de control (como una válvula en una tubería de gas natural) que pueden ser abiertos o cerrados. Los '+' son nodos (como las T de la tubería), y supongo que el pozo y la casa también son nodos.

Me gustaría saber si cierro un punto de control arbitrario (por ejemplo, C) si el pozo y la casa todavía están conectados (otros puntos de control también pueden estar cerrados). Por ejemplo, si B, K y D están cerrados, todavía tenemos un camino a través de AEJFCGLM, y al cerrar C se desconectará el Pozo y la Casa. Por supuesto; si solo D se cerró, cerrar solo C no desconecta la casa.

Otra forma de decir esto es C un bridge / cut edge / isthmus?

Podría tratar cada punto de control como un peso en el gráfico (ya sea 0 para abrir o 1 para cerrado); y luego encuentre el camino más corto entre el pozo y la casa (un resultado> = 1 indicaría que estaban desconectados. Hay varias maneras en que puedo cortocircuitar el algoritmo para encontrar el camino más corto también (por ejemplo, descartar un camino una vez que alcanza 1, detener buscando una vez que tenemos CUALQUIER ruta que conecte el Pozo y la Casa, etc.). Y por supuesto, también puedo poner un límite artificial sobre cuántos saltos comprobar antes de darme por vencidos.

Alguien debe haber clasificado este tipo de problema antes, solo me falta el nombre.

Publicado el 09/12/2008 a las 22:41
fuente por usuario
En otros idiomas...                            


10 respuestas

votos
31

Su descripción parece indicar que solo está interesado en si dos nodos están conectados, sin encontrar el camino más corto.

Encontrar si dos nodos están conectados es relativamente fácil:

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoList
  Add it to doneList
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

Si utiliza una tabla hash o algo similar para toDoSet y doneSet, creo que este es un algoritmo lineal.

Tenga en cuenta que este algoritmo es básicamente la porción de marca de la recolección de elementos no utilizados.

Respondida el 09/12/2008 a las 22:52
fuente por usuario

votos
6

Consulte http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , su ventanilla única para todos los problemas relacionados con los gráficos. Creo que su problema es, de hecho, solucionable en tiempo cuadrático.

Respondida el 09/12/2008 a las 22:45
fuente por usuario

votos
5

No necesita el algoritmo de Dijkstra para este problema, ya que utiliza un Heap que no es necesario e introduce un factor de registro (N) para su complejidad. Esta es solo la primera búsqueda de ancho: no incluya los bordes cerrados como bordes.

Respondida el 09/12/2008 a las 23:08
fuente por usuario

votos
3

El problema de encontrar el camino más corto no es NP completo. Se llama el problema de la ruta más corta (originalmente suficiente) y existen algoritmos para resolver muchas variaciones diferentes de la misma.

El problema de determinar si dos nodos están conectados tampoco es NP-completo. Puede utilizar una primera búsqueda en profundidad comenzando en cualquiera de los nodos para determinar si está conectado al otro nodo.

Respondida el 09/12/2008 a las 22:51
fuente por usuario

votos
2

Suponiendo que tienes una matriz de adyacencia:

bool[,] adj = new bool[n, n];

Donde bool [i, j] = verdadero si hay un camino abierto entre i y j y bool [i, i] = falso.

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

Aquí hay una versión recursiva del algoritmo anterior (escrito en Ruby):

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end
Respondida el 09/12/2008 a las 23:23
fuente por usuario

votos
2

Para mí, parece que estás buscando una solución, pero es posible que haya entendido mal el problema. Si le gusta decir y le da los bordes cerrados 1 como el peso, puede aplicar el algoritmo de Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Esto debería resolver su problema en O (E * lg (V))

Respondida el 09/12/2008 a las 22:49
fuente por usuario

votos
2

no NP-completo, resuelto con una solución conocida - Algoritmo de Dijkstra

Respondida el 09/12/2008 a las 22:43
fuente por usuario

votos
0

Si todo lo que necesita es para determinar si 2 nodos están conectados puede utilizar conjuntos en cambio, que es más rápido que los algoritmos de grafos.

  1. Dividir todo el gráfico en los bordes. Añadir a cada borde de un conjunto.
  2. En la siguiente iteración, dibujar bordes entre los nodos 2 exterior del borde realizados en el paso 2. Esto significa la adición de nuevos nodos (con sus correspondientes conjuntos) al conjunto del borde original era de. (Fusión básicamente establecido)
  3. Repetir 2 hasta los 2 nodos que buscas están en el mismo conjunto. También tendrá que hacer una comprobación después del paso 1 (si acaso los 2 nodos son adyacentes).

Al principio los nodos serán cada una en su conjunto,

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

Como el algoritmo avanza y fusiona los conjuntos, que sea relativamente mitades de la entrada.

En el ejemplo anterior que estaba buscando para ver si había un camino entre O1 y O2. He encontrado este camino sólo al final después de la fusión de todos los bordes. Algunos gráficos pueden tener componentes separados (desconectados) lo que implica que no vas a ser capaz de tener un juego al final. En tal caso, se puede utilizar este algoritmo para comprobar la conectividad e incluso contar el número de componentes en un gráfico. El número de componentes es el número de juegos que son capaces de obtener cuando el algoritmo termina.

Una posible gráfico (para el árbol de arriba):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
Respondida el 17/12/2011 a las 04:14
fuente por usuario

votos
0

¡Dijkstra es exagerado! Solo use la primera búsqueda de amplitud desde A para buscar el nodo al que desea llegar. Si no puede encontrarlo, no está conectado. La complejidad es O (nm) para cada búsqueda, que es menor que Dijkstra.

Algo relacionado es el problema de flujo máximo / corte mínimo. Búscalo, podría ser relevante para tu problema.

Respondida el 12/12/2008 a las 15:11
fuente por usuario

votos
-1

Cualquier gráfico algoritmo de ruta más corta será una exageración si todo lo que necesita es encontrar si un nodo está conectado a otro. Una buena biblioteca de Java que realiza que es JGraphT . Su uso es bastante simple, este es un ejemplo de un gráfico de enteros:

public void loadGraph() {
    // first we create a new undirected graph of Integers
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

    // then we add some nodes
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addVertex(5);
    graph.addVertex(6);
    graph.addVertex(7);
    graph.addVertex(8);
    graph.addVertex(9);
    graph.addVertex(10);
    graph.addVertex(11);
    graph.addVertex(12);
    graph.addVertex(13);
    graph.addVertex(14);
    graph.addVertex(15);
    graph.addVertex(16);

    // then we connect the nodes
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.addEdge(9, 10);
    graph.addEdge(10, 11);
    graph.addEdge(11, 12);
    graph.addEdge(13, 14);
    graph.addEdge(14, 15);
    graph.addEdge(15, 16);

    // finally we use ConnectivityInspector to check nodes connectivity
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph);

    debug(inspector, 1, 2);
    debug(inspector, 1, 4);
    debug(inspector, 1, 3);
    debug(inspector, 1, 12);
    debug(inspector, 16, 5);
}

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) {
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

Este lib también ofrece todos los caminos más cortos algoritmos también.

Respondida el 14/11/2016 a las 03:34
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more