Come determinare se due nodi sono connessi?

Question

Sono preoccupato che questo potrebbe funzionare su un problema NP-Complete. Spero che qualcuno possa darmi una risposta sul fatto che lo sia o meno. E sto cercando più di una risposta che solo sì o no. Mi piacerebbe sapere perché. Se si può dire: "Questo è fondamentalmente questo problema 'x', che è/non è. (Link wikipedia) NP-completo"

(No questo non è compito)

Esiste un modo per determinare se due punti sono collegati su un grafo arbitrario non diretto. ad esempio, il seguente

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

Punto A se M (senza 'I') sono punti di controllo (come una valvola in un tubo del gas naturale) che possono essere aperti o chiusi. I '+' sono nodi (come i pipe T's), e suppongo che anche Well e the House siano anche nodi.

Mi piacerebbe sapere se cancello un punto di controllo arbitrario (ad es. C) se il pozzo e la casa sono ancora collegati (altri punti di controllo possono anche essere chiusi). Ad esempio, se B, K e D sono chiusi, abbiamo ancora un percorso attraverso A-E-J-F-C-G-L-M, e chiudendo C si disconnetterà il Pozzo e la Casa. Ovviamente; se solo D fosse chiuso, chiudendo solo C non disconnetterebbe la casa.

Un altro modo di mettere questo è C a bridge/cut edge/isthmus?

Potrei trattare ciascun punto di controllo come un peso sul grafico (0 per aperto o 1 per chiuso); e poi trova il percorso più breve tra Well e House (un risultato> = 1 indica che sono stati disconnessi. Ci sono vari modi in cui posso cortocircuitare l'algoritmo per trovare anche il percorso più breve (ad esempio, scartare un percorso una volta che raggiunge 1, stop Cercando una volta che abbiamo QUALSIASI percorso che colleghi il Pozzo e la Casa, ecc.) E naturalmente, posso anche inserire un limite artificiale sul numero di salti da controllare prima di arrendersi

Qualcuno deve aver classificato questo tipo di problema prima, mi manca solo il nome

Answer 1

Vedi http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, la tua su e ferma il negozio per tutti i problemi relativi al grafico. Credo che il tuo problema sia risolvibile in tempo quadratico.

Answer 2

non NP-completo, risolto con una soluzione ben nota -. Dijkstra's Algorithm

Answer 3

Per me sembra che tu abbia una soluzione, ma è possibile che abbia frainteso il problema. Se ti piace dire quello che dici, e dare i bordi chiusi 1 come peso, puoi semplicemente applicare l'algoritmo di Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. Questo dovrebbe risolvere il tuo problema in O (E * lg (V))

Answer 4

Il problema di trovare il percorso più breve non è NP-completo. Si chiama Shortest Path Problem (in origine abbastanza) e ci sono algorithms per risolvere molte diverse varianti di esso.

Il problema di determinare se due nodi sono connessi non è NP-completo. È possibile utilizzare una prima ricerca di profondità a partire da entrambi i nodi per determinare se è connessa all'altro nodo.

Answer 5

La tua descrizione sembra indicare che ti interessa solo sapere se due nodi sono connessi, non trovare il percorso più breve.

Trovare se sono collegati due nodi è relativamente facile:

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. 

Se si utilizza una tabella hash o qualcosa di simile per toDoSet e doneSet, credo che questo sia un algoritmo lineare.

Si noti che questo algoritmo è fondamentalmente la parte di contrassegno della garbage collection mark-and-sweep.

Answer 6

Non è necessario l'algoritmo di Dijkstra per questo problema, poiché utilizza un heap che non è necessario e introduce un fattore di registro (N) per la complessità. Questa è solo una ricerca per ampiezza - non includere i bordi chiusi come bordi.

Answer 7

Supponendo che si dispone di una matrice di adiacenza:

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

Dove bool [i, j] = true se c'è un percorso aperto tra i e j e bool [i, i] = false.

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

Ecco una versione ricorsiva dell'algoritmo sopra (scritto in 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

Dijkstra è eccessivo !! Basta usare la ricerca per ampiezza da A per cercare il nodo che si desidera raggiungere. Se non riesci a trovarlo, non è collegato. La complessità è O (nm) per ogni ricerca, che è inferiore a Dijkstra.

Un po 'correlato è il problema max-flow/min-cut. Cercare, potrebbe essere rilevante per il tuo problema.

Answer 9

Se tutto ciò che serve è determinare se 2 nodi sono collegati, è possibile utilizzare invece set, che è più veloce di algoritmi di grafi.

1. Dividi l'intero grafico in bordi. Aggiungi ogni spigolo a un set.
2. Alla successiva iterazione, traccia i bordi tra i 2 nodi esterni del bordo che hai fatto nel passaggio 2. Ciò significa aggiungere nuovi nodi (con i loro set corrispondenti) al set dal quale era il bordo originale. (Fondamentalmente impostare la fusione)
3. Ripeti 2 finché i 2 nodi che stai cercando sono nello stesso set. Sarà inoltre necessario eseguire un controllo dopo il punto 1 (nel caso in cui i 2 nodi siano adiacenti).

Dapprima i nodi saranno ciascuno nel suo insieme,

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 

Poiché l'algoritmo procede e fonde i set, relativamente dimezza l'input.

Nell'esempio sopra, stavo cercando di vedere se c'era un percorso tra o1 e o2. Ho trovato questo percorso solo alla fine dopo aver unito tutti i bordi. Alcuni grafici possono avere componenti separati (scollegati) che comportano il fatto che non sarà possibile avere un set alla fine. In tal caso è possibile utilizzare questo algoritmo per verificare la connettività e persino contare il numero di componenti in un grafico. Il numero di componenti è il numero di set che è possibile ottenere al termine dell'algoritmo.

Una possibile grafico (per l'albero sopra):

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

Answer 10

Qualsiasi grafico algoritmo di percorso più breve sarà eccessivo se tutto ciò che serve è di trovare se un nodo è collegato ad un altro. Una buona libreria Java che lo comporti è JGraphT. È uso è abbastanza semplice, ecco un esempio di un grafico intero:

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

Questo lib offre tutti i brevi percorsi algoritmi pure.