Wie bestimmt man, ob zwei Knoten miteinander verbunden sind?

Question

Ich mache mir Sorgen, dass dies an einem NP-vollständigen Problem arbeiten könnte. Ich hoffe, dass mir jemand eine Antwort geben kann, ob es das ist oder nicht. Und ich suche nach mehr als nur Ja oder Nein. Ich würde gerne wissen warum. Wenn Sie sagen können: "Dies ist im Grunde genommen das Problem 'x', das NP-vollständig ist/nicht ist. (Wikipedia-Link)"

(Nein, das ist keine Hausaufgabe)

Gibt es eine Möglichkeit festzustellen, ob zwei Punkte in einem beliebigen nicht gerichteten Graphen verbunden sind. z.B., der folgende

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

Die Punkte A bis M (kein 'I') sind Steuerpunkte (wie ein Ventil in einer Erdgasleitung), die entweder geöffnet oder geschlossen sein können. Die '+'s sind Knoten (wie Rohrgabelungen) und ich denke, der Brunnen und das Haus sind auch Knoten.

Ich möchte wissen, ob ich einen beliebigen Steuerpunkt schließe (z.B. C), ob der Brunnen und das Haus immer noch verbunden sind (andere Steuerpunkte können auch geschlossen sein). Z.B., wenn B, K und D geschlossen sind, haben wir immer noch einen Pfad über A-E-J-F-C-G-L-M und das Schließen von C würde den Brunnen und das Haus trennen. Natürlich wenn nur D geschlossen war, würde das Schließen von nur C das Haus nicht trennen.

Eine andere Möglichkeit, dies auszudrücken, ist C eine Brücke/Schnittkante/Isthmus?

Ich könnte jeden Steuerpunkt als Gewicht im Graphen behandeln (entweder 0 für geöffnet oder 1 für geschlossen) und dann den kürzesten Pfad zwischen Brunnen und Haus finden (ein Ergebnis >= 1 würde anzeigen, dass sie getrennt sind). Es gibt verschiedene Möglichkeiten, wie ich den Algorithmus zur Suche des kürzesten Pfades umgehen kann (z.B., einen Pfad verwerfen, sobald er 1 erreicht, die Suche stoppen, sobald wir einen beliebigen Pfad haben, der den Brunnen und das Haus verbindet, usw.). Und natürlich könnte ich auch eine künstliche Grenze festlegen, wie viele Sprünge zu überprüfen sind, bevor ich aufgebe.

Es muss jemand dieses Problem bereits klassifiziert haben, mir fehlt nur der Name.

Answer 1

Jeder Graph-Shortest-Path-Algorithmus ist überdimensioniert, wenn alles, was Sie brauchen, ist zu finden, ob ein Knoten mit einem anderen verbunden ist. Eine gute Java-Bibliothek, die das erreicht, ist JGraphT. Die Verwendung ist ziemlich einfach, hier ist ein Beispiel für einen Integer-Graph:

public void loadGraph() {
    // zuerst erstellen wir einen neuen ungerichteten Graphen von Integers
    UndirectedGraph graph = new SimpleGraph<>(DefaultEdge.class);

    // dann fügen wir einige Knoten hinzu
    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);

    // dann verbinden wir die Knoten
    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);

    // schließlich verwenden wir den ConnectivityInspector, um die Knotenverbindungen zu überprüfen
    ConnectivityInspector 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 inspector, Integer n1, Integer n2) {
    System.out.println(String.format("Sind [%s] und [%s] verbunden? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

Diese Bibliothek bietet auch alle kürzesten Pfadalgorithmen an.