graph-theory - grado - grafo aleatorio

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

Question

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.

Answer 1

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

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

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

Si todo lo que necesita es determinar si 2 nodos están conectados, puede usar conjuntos en su lugar, lo que es más rápido que los algoritmos de gráficos.

1. Divide todo tu gráfico en los bordes. Agregue cada borde a un conjunto.
2. En la siguiente iteración, dibuje los bordes entre los 2 nodos externos del borde que hizo en el paso 2. Esto significa agregar nuevos nodos (con sus conjuntos correspondientes) al conjunto del borde original. (básicamente establecer fusión)
3. Repite 2 hasta que los 2 nodos que estás buscando estén en el mismo conjunto. También deberá hacer una comprobación después del paso 1 (en caso de que los 2 nodos estén adyacentes).

Al principio tus nodos estarán cada uno 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

A medida que el algoritmo progresa y fusiona los conjuntos, reduce a la mitad la entrada.

En el ejemplo anterior, estaba buscando si había un camino entre o1 y o2. Encontré esta ruta solo al final después de fusionar todos los bordes. Algunos gráficos pueden tener componentes separados (desconectados) lo que implica que no podrá tener un conjunto al final. En tal caso, puede usar este algoritmo para probar la conectividad e incluso contar el número de componentes en un gráfico. La cantidad de componentes es la cantidad de conjuntos que puede obtener cuando finaliza el algoritmo.

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

o-o1-o-o-o2
  |    |
  o    o
       |
       o

Answer 9

Cualquier algoritmo de ruta más corto del gráfico será excesivo si todo lo que necesita es encontrar si un nodo está conectado a otro. Una buena biblioteca de Java que logra eso es JGraphT . Su uso es bastante simple, aquí hay un ejemplo de un gráfico entero:

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)));
}

Esta lib también ofrece todos los algoritmos de rutas más cortas.

Answer 10

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