Ich bekomme einen ungerichteten Baum im üblichen graphentheoretischen Sinne. Wenn ein Scheitelpunkt und eine Kante , die auf einfallen, muss ich Fragen der Form beantworten, die jedes Blatt von , das von aus erreichbar ist, mit einem Pfad, der , und keine anderen Kanten ? Informeller ist die Einschränkung, dass wir, wenn die Kante gegeben ist, nur in diese Richtung gehen können.
Ich kann einfach eine DFS durchführen und ein gefundenes Blatt zurückgeben. Ich denke, dies würde Zeit dauern , wobei der Durchmesser von . Ich möchte jedoch eine Anfrage in Zeit beantworten . Außerdem möchte ich nur eine lineare Vorverarbeitungszeit zulassen. Meine Idee, dies zu erreichen, bestand darin, eine DFS zu verwenden, Blätter zu beschriften und dann Kanten zu beschriften, wenn die Suche zurückverfolgt wird. Diese Idee könnte mit zusätzlichem Aufwand funktionieren, aber ich bin mir über die Details nicht sicher.
"Graph Erreichbarkeit" ergab einige Ergebnisse, aber vielleicht haben sie es mit komplexeren Problemen zu tun. Ich bin mit jeder Methode zufrieden, die die Vorverarbeitungszeit von und die Fragen in der Zeit von beantwortet .
quelle
Antworten:
Ja, ich denke du kannst das inO(1) Zeit. Ich skizziere unten eine Methode. Es gibt wahrscheinlich einen einfacheren Weg, aber das Folgende sollte ausreichen.
Vorverarbeitung. Ich gehe davon aus, dass wir Ihren Baum als einen verwurzelten Baum mit einer Wurzel betrachten können. Kommentieren Sie in der Vorverarbeitung jeden internen Knotenw mit einem Beispiel eines Blattes, das ein Nachkomme von ist w . Dies kann in erfolgenO(n+m) Vorverarbeitungszeit mit einem sehr einfachen Top-Down-Traversal (DFS).
Definieren Sie auchp∗(⋅) rekursiv wie folgt: wenn w hat also irgendwelche Geschwister p∗(w)=w ;; Andernfalls,p∗(w)=p∗(v) wo v ist der Elternteil von w ;; undp∗(r)=r , wo r ist die Wurzel von T . Auf Englisch,p∗(w) ist definiert als der Knoten, der durch Beginnen bei erhalten wird w und weiter nach oben, bis wir einen Knoten erreichen, der zwei oder mehr Kinder (oder die Wurzel) hat. In der Vorverarbeitung berechnen wir den Wert vonp∗(w) für jeden Knoten w und speichern Sie es in Verbindung mit w . Auch dies kann in berechnet werdenO(n+m) Zeit.
Beantwortung einer Anfrage. Hier erfahren Sie, wie Sie die Abfrage beantworten und jedes Blatt zurückgeben, von dem aus Sie erreichen könnenv mit einem Pfad einschließlich (u,v) und keine anderen Kanten, die auffallen v ::
Fall 1: Angenommenu ist ein Kind von v . Die Beantwortung Ihrer Anfrage bedeutet dann, dass jedes Blatt zurückgegeben wird, von dem ein Nachkomme stammtu . Dies kann in erfolgenO(1) Zeit mit der Anmerkung auf u .
Fall 2: Angenommenu ist der Elternteil von v , und u hat mindestens ein weiteres Kind. Dann schauen Sie sich ein anderes Kind von anu , nennen w . Die Beantwortung Ihrer Anfrage bedeutet dann, dass jedes Blatt zurückgegeben wird, von dem ein Nachkomme stammtw . Dies kann in erfolgenO(1) Zeit mit der Anmerkung auf w .
Fall 3: Angenommenu ist der Elternteil von v , und u hat keine anderen Kinder. Dann lassu′=p∗(u) und lass w sei ein anderes Kind von u′ (kein Vorfahr von v ). Die Beantwortung Ihrer Anfrage bedeutet dann, dass jedes Blatt zurückgegeben wird, von dem ein Nachkomme stammtw . Dies kann in erfolgenO(1) Zeit mit der Anmerkung auf w .
In allen drei Fällen kann die Antwort auf die Abfrage in berechnet werdenO(1) Zeit.
quelle