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

Nicht NP-vollständig, gelöst mit einer bekannten Lösung - Dijkstras Algorithmus

Answer 2

Mir scheint es, als ob du auf eine Lösung gekommen bist, aber es ist möglich, dass ich das Problem falsch verstanden habe. Wenn du tust, was du sagst, und die geschlossenen Kanten mit 1 als Gewicht angibst, kannst du einfach den Dijkstra-Algorithmus anwenden, http://de.wikipedia.org/wiki/Dijkstra-Algorithmus. Das sollte dein Problem in O(E*lg(V)) lösen.

Answer 3

Dijkstras ist übertrieben!! Verwenden Sie einfach Breath-First-Suche von A, um den Knoten zu suchen, den Sie erreichen möchten. Wenn Sie ihn nicht finden können, ist er nicht verbunden. Die Komplexität beträgt O(nm) für jede Suche, was weniger als Dijkstra ist.

Etwas verwandt ist das Max-Flow/Min-Cut-Problem. Schau es dir an, es könnte relevant für dein Problem sein.

Answer 4

Wenn Sie nur feststellen müssen, ob 2 Knoten verbunden sind, können Sie stattdessen Sets verwenden, die schneller als Graphalgorithmen sind.

1. Teilen Sie Ihren gesamten Graphen in Kanten auf. Fügen Sie jede Kante einem Set hinzu.
2. In der nächsten Iteration zeichnen Sie Kanten zwischen den 2 äußeren Knoten der Kante, die Sie in Schritt 2 erstellt haben. Dies bedeutet, dass Sie neue Knoten (mit ihren entsprechenden Sets) zum Set hinzufügen, aus dem die ursprüngliche Kante stammte. (im Grunde Set-Verschmelzung)
3. Wiederholen Sie Schritt 2, bis die 2 gesuchten Knoten im selben Set sind. Sie müssen auch eine Überprüfung nach Schritt 1 durchführen (falls die 2 Knoten benachbart sind).

Zu Beginn werden Ihre Knoten jeweils in ihrem eigenen Set sein,

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

Während der Algorithmus fortschreitet und die Sets verschmilzt, halbiert er relativ gesehen die Eingabe.

In obigem Beispiel habe ich überprüft, ob es einen Pfad zwischen o1 und o2 gibt. Ich habe diesen Pfad erst am Ende gefunden, nachdem alle Kanten zusammengeführt wurden. Einige Graphen können separate Komponenten (nicht verbunden) haben, dies bedeutet, dass Sie am Ende kein Set erhalten. In einem solchen Fall können Sie diesen Algorithmus verwenden, um die Verbundenheit zu testen und sogar die Anzahl der Komponenten in einem Graphen zu zählen. Die Anzahl der Komponenten ist die Anzahl der Sets, die Sie erhalten, wenn der Algorithmus beendet ist.

Ein möglicher Graph (für den obigen Baum):

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

Answer 5

Ich sehe, dass du deine Antwort hast, dass es definitiv nicht NP-vollständig ist und dies auch eine sehr alte Frage ist.

Dennoch werde ich einfach einen anderen Ansatz vorschlagen, um das Problem zu betrachten. Du könntest dafür disjunkte Mengen verwenden. In den meisten Fällen wird der Ansatz für das gegebene Szenario zu einer besseren Zeit führen als eine Graphtraversierung (das beinhaltet konstante Zeit für einen großen Teil der Tests). Allerdings könnte der Aufbau des Graphen eine gute Menge Zeit in Anspruch nehmen, wenn Union nach Rang oder Pfadkomprimierung verwendet wird.

Du kannst mehr über die Datenstruktur hier nachlesen.