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

Nehmen wir an, wir haben ein einfaches ungerichtetes Diagramm angegeben $G$ haben $N$ Knoten und $M$bidirektionale Kanten. Für gegeben$x$ 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 $y$Wenn 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?

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 $p_1, \dots p_n$ von $x$ zu $y$ im $O(|V|+|E|)$. Wenn kein solcher Pfad vorhanden ist, antworten Sie$\textsf{NO}$. 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 Pfades$p_1$Wählen Sie eine zufällige Kante aus $p_1$ anders als der, mit dem es verbunden ist $p_2$und starten Sie von dort aus eine DFS. Wenn Sie einen markierten Knoten erreichen, antworten Sie$\textsf{NO}$Wenn 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 erreichen$p_n$. Wenn Sie den Vorgang beenden, ohne jemals zu antworten$\textsf{NO}$, Antworten $\textsf{YES}$. Das gesamte Verfahren hat die Kosten einer DFS,$O(|V|+|E|)$, daher ist die Gesamtzeit $O(|V|+|E|)$.

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

Wenn es einen Pfad von der Quelle gibt $x$zu einem bestimmten Zyklus widerspricht es nicht immer der Existenz eines einzigen einfachen Pfades. Schauen Sie sich das folgende Beispiel an:

Hier gibt es einen Zyklus, von dem aus man erreichen kann $x$ und $y$. Dieses Problem kann in gelöst werden$O(|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 von$x$ 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ören$x$ zu $y$ mit der gleichen Entfernung zu $x$dann gibt es mindestens zwei kürzeste Wege, sonst ist es einzigartig. Sie können alle Nachbearbeitungen in durchführen$O(|V|)$.

Führen Sie eine Tiefensuche durch, die in beginnt $x$und 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.