¿Cómo se determina 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 se puede decir, "Esto es básicamente este problema 'X' que es/no es NP-completo. (Enlace Wikipedia)"

(No, esto no es tarea)

¿Hay una manera de determinar si dos puntos están conectados en un gráfico arbitrario no dirigido. por ejemplo, la siguiente

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

Puntos A pesar de que M (no 'I') son los puntos de control (como una válvula en una tubería de gas natural) que puede ser abierta o cerrada. 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 A-E-J-F-C-G-L-M, 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 expresar esto, ¿es C un puente/borde cortado/istmo?

Podría tratar cada punto de control como un peso en el gráfico (ya sea 0 para abrir o 1 para cerrar); 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 conecta el Pozo y la Casa, etc.) Y por supuesto, también puedo poner un límite artificial sobre cuántos saltos revisar antes de rendirme.

Alguien debe haber clasificado este tipo del problema antes, estoy sólo falta el nombre

Answer 1

Ver http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, en su e pare la tienda para todos los problemas relacionados con los gráficos. Creo que su problema es, de hecho, solucionable en tiempo cuadrático.

Answer 2

no NP-completo, resuelto con una solución bien conocida -. Dijkstra's Algorithm

Answer 3

Para mí, parece que estás buscando una solución, pero es posible que haya entendido mal el problema. Si le gusta decir y 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 4

El problema de encontrar la ruta más corta no es NP-completo. Se llama el problema de ruta más corta (originalmente suficiente) y hay algorithms 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 5

Su descripción parece indicar que está interesado solamente en si dos nodos están conectados, no 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 esto es un algoritmo lineal.

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

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

Asumiendo que usted tiene una matriz de adyacencia:

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

Dónde 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í es 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 

Answer 8

de Dijkstra es un exceso !! Simplemente use la primera búsqueda de ancho 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 9

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

1. Divida todo el 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 la 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 los nodos será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 

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

En el ejemplo anterior estaba buscando para ver 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.

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

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

Answer 10

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 logra eso 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.