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

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$

algorithms graphs graph-traversal saadtaame
quelle

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

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

@ 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

. Noch besser ist es, wenn

und

die Eigenschaft erfüllen und der Knoten

der letzte in

verarbeitete Knoten ist und in

die Suche in

beginnt , dann wird die Brückenkante hinzugefügt

G = (V, E)

$G = (V,E)$

= v

$= v$

G_{1}

$G_1$

G_{2}

$G_2$

v_{1}

$v_1$

G_{1}

$G_1$

v_{2}

$v_2$

G_{2}

$G_2$

einen Graphen, der die Eigenschaft erfüllt. Ersetzen von

(v_{1}, v_{2})

$(v_1, v_2)$

v_{1}

$v_1$ durch

funktioniert auch, denke ich.

v_{2}

$v_2$

Saadtaame

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

hinzufügen . Hier ist mein Satz: Gegeben ein Graph

, wenn

so dass

v

$v$

v

$v$

G = (V, E)

$G=(V,E)$

\forall x \in V

$\forall x \in V$

\exists y, z, w \in V

$\exists y,z,w \in V$

(y, x), (z, y), (x, w) \in E

$(y,x),(z,y),(x,w) \in E$ dann

(x, z) \in E ⟹

$(x,z) \in E \implies$ die Eigenschaft gilt für

. Der nächste Schritt besteht darin, diesen Satz zu beweisen oder zu widerlegen.

G

$G$

Saadtaame

Antworten:

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

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.