Diagramme, die bewirken, dass DFS und BFS Knoten in genau derselben Reihenfolge verarbeiten

11

Bei einigen Diagrammen verarbeiten DFS- und BFS-Suchalgorithmen Knoten in genau derselben Reihenfolge, vorausgesetzt, beide beginnen am selben Knoten. Zwei Beispiele sind Diagramme, die Pfade sind, und Diagramme, die sternförmig sind (Bäume der Tiefe mit einer beliebigen Anzahl von Kindern). Gibt es eine Möglichkeit, Diagramme zu kategorisieren, die diese Eigenschaft erfüllen?1

saadtaame
quelle
6
Beachten Sie, dass dies in beiden Fällen nur funktioniert, wenn Sie an einem bestimmten Knoten beginnen. Wenn Sie beispielsweise einen zentralen Knoten auf einem langen Pfad auswählen, erhalten Sie unterschiedliche Ordnungen von DFS und BFS zurück.
Templatetypedef
1
Gibt es andere interessante Möglichkeiten als einen Stern oder einen Weg? Auf den ersten Blick scheint es so, als ob Sie, wenn Sie einen Scheitelpunkt sowohl mit einem Geschwister als auch mit einem Kind hätten, sofort unterschiedliche Durchquerungen erhalten. Entweder hat kein Scheitelpunkt Kinder (außer der Wurzel) und Sie erhalten einen Stern, oder kein Scheitelpunkt hat ein Geschwister und du bekommst einen Weg. Ich denke, eine Clique funktioniert auch, aber sie hat sowohl den Stern als auch den Pfad eingebettet.
Luke Mathieson
2
@ LukeMathieson Ich denke an einen Stern, bei dem das Kind ganz rechts die Wurzel eines anderen Sterns ist. Ich denke, das würde auch funktionieren. Wir können sogar eine allgemeine Aussage treffen: Wenn die Eigenschaft erfüllt, wenn die Suche am Knoten v∈V beginnt, dann auch ein Stern, dessen Kind ganz rechts = v ist . Noch besser ist es, wenn G 1 und G 2 die Eigenschaft erfüllen und der Knoten v 1 der letzte in G 1 verarbeitete Knoten ist und in v 2 die Suche in G 2 beginnt , dann wird die Brückenkante hinzugefügt ( vG=(V,E)=vG1G2v1G1v2G2 einen Graphen, der die Eigenschaft erfüllt. Ersetzen von v 1(v1,v2)v1 durch funktioniert auch, denke ich. v2
Saadtaame
2
Guter Punkt, es gibt also eine Art rechtsrekursive Komposition, bei der Sie das rechte Blatt des ersten Diagramms mit der Wurzel des zweiten identifizieren können.
Luke Mathieson
@LukeMathieson Es sieht so aus, als könnten Sie den Fall beheben, in dem ein Knoten ein Geschwister und ein Kind hat, indem Sie eine Kante zwischen diesem Kind und dem Elternteil von v hinzufügen . Hier ist mein Satz: Gegeben ein Graph G = ( V , E ) . x V , wenn y , z , w V, so dass ( y , x ) , ( z , y ) , ( x , w ) E.vvG=(V,E)xVy,z,wV(y,x),(z,y),(x,w)Edann (x,z)Edie Eigenschaft gilt für . Der nächste Schritt besteht darin, diesen Satz zu beweisen oder zu widerlegen. G
Saadtaame

Antworten:

6

Angenommen, unser BFS und dfs haben eine Regel, um von einem bestimmten Knoten aus zu beginnen, und in jeder Richtung besuchen sie zuerst den Knoten mit dem niedrigsten Grad:

DFS-BFS

Beginnen Sie mit dem am weitesten links liegenden schwarzen Knoten, dann besuchen (BFS und DFS) den am weitesten links liegenden roten Knoten, dann besuchen sie den nächsten schwarzen Knoten usw. Um dies allgemeiner zu gestalten, können Sie einige Pfade zwischen Dreiecken hinzufügen oder einen Stern hinzufügen nach dem Beenden von Dreiecken ...


quelle
Das ist unter Ihrer Annahme richtig. Sie haben tatsächlich einen guten Punkt angesprochen; Wir sollten angeben, in welcher Reihenfolge die Knoten zur Agenda hinzugefügt werden (Stapel oder Warteschlange), wenn sie vor einer Auswahl stehen.
Saadtaame
Wenn man bedenkt, dass LIFO und FIFO für die Planung DFS bzw. BFS ergeben, könnte man argumentieren, dass eine solche Planung (bei der die Planung möglicherweise nicht stapel- oder warteschlangenartig ist) weder eine Tiefen- noch eine Breitensuche ist Sie können in einigen Fällen seine Tendenz beschreiben, dem einen oder anderen zu ähneln.
Niel de Beaudrap
1
Ich denke, es kann in Form eines Stapels oder einer Warteschlange implementiert werden. Es ändert nichts daran, wie Dinge abgenommen werden (LIFO oder FIFO), es ändert die Reihenfolge, in der Kinder hinzugefügt werden (in diesem Fall der niedrigste Grad zuerst).
SamM
@NieldeBeaudrap actually this is just a structure to show that somewhere both ways are same.