Wykresy, które powodują, że DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności

W przypadku niektórych wykresów algorytmy wyszukiwania DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności, pod warunkiem, że oba rozpoczynają się w tym samym węźle. Dwa przykłady to wykresy będące ścieżkami i wykresy w kształcie gwiazdy (drzewa o głębokości z dowolną liczbą dzieci). Czy istnieje sposób kategoryzowania wykresów spełniających tę właściwość? $1$

algorithms graphs graph-traversal saadtaame
źródło

Zauważ, że w obu przypadkach działa to tylko wtedy, gdy zaczynasz od określonego węzła. Na przykład, jeśli wybierzesz centralny węzeł na długiej ścieżce, odzyskasz inne porządki z DFS i BFS.

templatetypedef

Czy są jakieś inne interesujące możliwości niż gwiazda lub ścieżka? Na pierwszy rzut oka wydaje się, że jeśli masz wierzchołek z rodzeństwem i dzieckiem, natychmiast dostajesz różne przejścia, więc albo żaden wierzchołek nie ma dzieci (oprócz korzenia) i dostajesz gwiazdę, lub żaden wierzchołek nie ma rodzeństwa i dostajesz ścieżkę. Chyba klika również działa, ale ma zarówno gwiazdę, jak i ścieżkę.

Luke Mathieson,

@LukeMathieson Mam na myśli gwiazdę z prawym dzieckiem będącą korzeniem innej gwiazdy. Myślę, że to też zadziała. Możemy nawet sformułować ogólne stwierdzenie: jeśli spełnia właściwość, gdy wyszukiwanie rozpoczyna się w węźle v∈V, to robi to również gwiazda, której skrajne prawe dziecko . Jeszcze lepiej, jeśli i spełniać nieruchomość i węzeł jest ostatnim przetwarzane i gdzie rozpoczyna wyszukiwania w , a następnie dodanie krawędzi mostka tworzy wykres, który spełnia nieruchomości. Wymiana przez działa również myślę.

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$

(v_{1}, v_{2})

$(v_1, v_2)$

v_{1}

$v_1$

v_{2}

$v_2$

saadtaame

Dobra uwaga, więc istnieje pewna rekurencyjna kompozycja, w której można zidentyfikować właściwy liść pierwszego wykresu z pierwiastkiem drugiego.

Luke Mathieson,

@LukeMathieson Wygląda na to, że możesz naprawić przypadek, w którym węzeł ma rodzeństwo i dziecko, dodając krawędź między tym dzieckiem a rodzicem . Oto moja propozycja: Biorąc pod uwagę wykres . , jeśli tak, że , a następnie własność zachodzi dla . Następnym krokiem jest udowodnienie lub obalenie tej propozycji.

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$

(x, z) \in E ⟹

$(x,z) \in E \implies$

G

$G$

saadtaame

Odpowiedzi:

Załóżmy, że nasz BFS i dfs mają regułę rozpoczynającą się od określonego węzła i w każdym dwukierunkowym odwiedzają najpierw węzeł o najniższym stopniu:

DFS-BFS

zacznij od lewego najbardziej czarnego węzła, następnie (BFS i DFS) odwiedź lewy najbardziej czerwony węzeł, następnie odwiedzą następny czarny węzeł i tak dalej, dla uogólnienia możesz dodać ścieżki między trójkątami lub gwiazdkę po zakończeniu trójkątów ...

źródło

Zgadza się to z twoim założeniem. Właściwie podniosłeś rację; powinniśmy określić, w jakiej kolejności węzły są dodawane do porządku dziennego (stosu lub kolejki) w obliczu wyboru.

saadtaame

Biorąc pod uwagę, że LIFO i FIFO do planowania dają odpowiednio DFS i BFS, można argumentować, że takie planowanie (w którym planowanie może nie być podobne do stosu lub kolejki) nie jest ani wyszukiwaniem głębokości, ani szerokości pierwszego - chociaż w niektórych przypadkach możesz opisać jego tendencję do przypominania jednego lub drugiego.

Niel de Beaudrap,

Myślę, że można to zaimplementować w postaci stosu lub kolejki. Nie zmienia sposobu zdejmowania rzeczy (LIFO lub FIFO), zmienia kolejność dodawania dzieci (w tym przypadku najpierw najniższy stopień).

SamM

@NieldeBeaudrap w rzeczywistości jest to tylko struktura pokazująca, że gdzieś oba sposoby są takie same.