Überprüfen Sie, ob es im Diagramm nur einen einfachen Pfad zwischen den Knoten x und y gibt

7

Nehmen wir an, wir haben ein einfaches ungerichtetes Diagramm angegeben G haben N Knoten und Mbidirektionale Kanten. Für gegebenx und y Wir möchten überprüfen, ob es in der Grafik nur einen einfachen Pfad zwischen ihnen gibt.

Ich dachte daran, dass wir alle Zyklen in der Grafik finden und bfs ausführen sollten x zu yWenn sich der Pfad nicht durch die Scheitelpunkte bewegt, die sich in einem Zyklus befinden, gibt es nur einen Pfad, und ansonsten gibt es mehr.

Gibt es eine andere Möglichkeit, dies zu überprüfen?

jemand12321
quelle
1
Mögliches Duplikat cs.stackexchange.com/questions/3078/…
Eugene
Es ist eine ähnliche Frage, aber meine Frage fragt nur, ob es nur eine oder mehrere gibt.
jemand12321
@ Eugene Sehr ähnlich, aber ich denke härter.
Raphael

Antworten:

5

Raphaels Vorschlag, den kürzesten Weg zu verwenden, ist richtig, aber komplexer als nötig.

Ihr Ansatz ist nicht durchführbar, die Anzahl der Zyklen hängt von der Größe der Eingabe ab.

Hier ist eine Skizze einer zeitlichen Lösung O(|V|+|E|).

Finde einen Weg p1,pn von x zu y im O(|V|+|E|). Wenn kein solcher Pfad vorhanden ist, antworten SieNO. Andernfalls markieren Sie alle Knoten im Pfad. Dieser Pfad ist in der Tat genau dann eindeutig, wenn kein Knoten in diesem Pfad einen nachfolgenden Knoten erreicht. Ausgehend vom ersten Knoten des Pfadesp1Wählen Sie eine zufällige Kante aus p1 anders als der, mit dem es verbunden ist p2und starten Sie von dort aus eine DFS. Wenn Sie einen markierten Knoten erreichen, antworten SieNOWenn Sie nie einen markierten Knoten erreichen, schneiden Sie diesen Zweig aus dem Diagramm aus und wählen Sie eine andere zufällige ausgehende Kante aus. Fahren Sie auf ähnliche Weise fort, bis alle ausgehenden Kanten erschöpft sind, und beginnen Sie dann erneut mit dem folgenden Knoten, bis Sie erreichenpn. Wenn Sie den Vorgang beenden, ohne jemals zu antwortenNO, Antworten YES. Das gesamte Verfahren hat die Kosten einer DFS,O(|V|+|E|), daher ist die Gesamtzeit O(|V|+|E|).

schnelle Sorte
quelle
Wenn Sie "diesen Zweig aus dem Diagramm ausschneiden" sagen, meinen Sie damit, dass Sie alle Kanten entfernen, die Sie durchlaufen haben? Was am Ende der DFS nicht wirklich auf einmal geschehen würde; Dies würde auf dem Rückweg "hoch" in der DFS selbst geschehen. Recht? Ich habe es mit ein wenig Nachdenken verstanden, aber es könnte möglicherweise klarer erklärt werden.
Wildcard
1
Auf welche der beiden Antworten von Raphael beziehen Sie sich? Oh, wahrscheinlich die, die vor Ihrer Antwort gepostet wurde, und nicht die, die danach gepostet wurde. :-) Zur Verdeutlichung bearbeitet.
David Richerby
@Wildcard: Ja, Sie würden eigentlich nichts "schneiden", ich habe es so geschrieben, weil ich das Gefühl hatte, dass es die Idee von dem gab, was ich versuchte, aber in einer tatsächlichen Implementierung gehe ich davon aus, dass Sie diese Knoten einfach irgendwie als markieren würden in der DFS selbst besucht.
Quicksort
2

Führen Sie einen k-kürzesten Pfad- Algorithmus mit ausk=2 und beobachten, ob es fehlschlägt.

Raphael
quelle
3
Ist das nicht übertrieben? Dynamische Programmierung löst es in O (| V | + | E |)
Quicksort
@quicksort Ahh, ich habe die Frage auf kürzeste Wege in meinem Kopf erweitert, sorry. : D Bitte fügen Sie eine weitere Antwort hinzu!
Raphael
2

Wenn es einen Pfad von der Quelle gibt xzu einem bestimmten Zyklus widerspricht es nicht immer der Existenz eines einzigen einfachen Pfades. Schauen Sie sich das folgende Beispiel an: Geben Sie hier die Bildbeschreibung ein

Hier gibt es einen Zyklus, von dem aus man erreichen kann x und y. Dieses Problem kann in gelöst werdenO(|V|+|E|).

Sie können BFS ausführen, um die kürzeste Entfernung von zu finden x zu jedem Scheitelpunkt im Diagramm und das gleiche von y. Ein Knoten gehört zum kürzesten Weg vonx zu y dann und nur dann, wenn

distance(x,u)+distance(u,y)=distance(x,y)
Um zu überprüfen, ob es einen einzelnen Pfad gibt, überprüfen Sie, ob gültige Knoten im kürzesten Pfad in jeder Entfernung höchstens einmal vorkommen. Dies ist der Fall, wenn mindestens zwei Knoten zu einem kürzesten Pfad von gehörenx zu y mit der gleichen Entfernung zu xdann gibt es mindestens zwei kürzeste Wege, sonst ist es einzigartig. Sie können alle Nachbearbeitungen in durchführenO(|V|).
Marcelo Fornet
quelle
Schauen Sie, wir wollen nicht haben, ob es zwei gleiche Entfernungspfade gibt, sondern nur, um zu überprüfen, ob es zwei verschiedene Pfade gibt
jemand12321
Ich verstehe, ich weiß nicht, warum ich dachte, dass beide Pfade von minimaler Länge sind. Wie auch immer, ich hoffe, Sie finden das obige Beispiel nützlich, es gilt immer noch.
Marcelo Fornet
0

Führen Sie eine Tiefensuche durch, die in beginnt xund kommentieren Sie Kanten danach, ob es sich um Baum-, Rücken- oder Kreuzkanten handelt (vgl. z. B. hier ).

Es gibt mehr als einen einfachen Weg von x zu y genau dann, wenn (mindestens) ein Knoten auf dem Pfad von ist x zu y Verwenden Sie nur Baumkanten (dh den von DFS gefundenen Pfad), die auf eine Hinter- oder Querkante treffen.

Raphael
quelle