Jakie jest znaczenie „szerokość” przy pierwszym wyszukiwaniu?

Uczyłem się o pierwszym wyszukiwaniu szerokości i przyszło mi do głowy pytanie, dlaczego tak nazywa się BFS. W książce Wprowadzenie do algorytmów CLRS przeczytałem następujący powód:

Poszukiwanie szerokości jest tak nazwane, ponieważ równomiernie rozszerza granicę między odkrytymi i nieodkrytymi wierzchołkami na całej szerokości granicy.

Nie jestem jednak w stanie zrozumieć znaczenia tego stwierdzenia. Jestem zdezorientowany tym słowem „granica” i szerokością tej granicy.

Czy ktoś może więc odpowiedzieć na to pytanie w sposób łatwy do zrozumienia dla takiego początkującego jak ja?

Rozważ strukturę danych użytą do reprezentowania wyszukiwania. W BFS używasz kolejki. Jeśli natrafisz na niewidoczny węzeł, dodajesz go do kolejki.

„Granica” to zbiór wszystkich węzłów w strukturze danych wyszukiwania. Kolejka będzie przechodzić kolejno przez wszystkie węzły na granicy, w ten sposób przechodząc przez całą szerokość granicy. DFS zawsze usunie ostatnio wykryty stan ze stosu, dzięki czemu zawsze będzie iterował najgłębszą część granicy.

Rozważ poniższy obrazek. Zwróć uwagę, jak DFS przechodzi prosto do najgłębszych części drzewa, podczas gdy BFS przechodzi przez szerokość każdego poziomu.

Zdjęcie tutaj

Cytat, który podajesz, mówi „granica między odkrytymi a nieodkrytymi wierzchołkami”. A więc jest to granica, o której mówi autor: granica między odkrytymi a nieodkrytymi wierzchołkami. Masz kilka wierzchołków, których jeszcze niczego nie widziałeś. Masz także kilka wierzchołków, dla których widziałeś wszystko. A potem masz między nimi wierzchołki. Są to wierzchołki, na które spojrzałeś, ale nie załadowałeś jeszcze wszystkich ich dzieci. To jest granica.

Omawia to dalej na temat:

Aby śledzić postęp, kolory BFS każdego wierzchołka są białe, szare lub czarne. Wszystkie wierzchołki zaczynają się na biało, a później mogą stać się szare, a następnie czarne. Wierzchołek jest wykrywany przy pierwszym napotkaniu podczas przeszukiwania, kiedy to staje się inny niż biały. W związku z tym odkryto szare i czarne wierzchołki, ale BFS rozróżnia je, aby wyszukiwanie przebiegało w sposób BF.
...
każdy wierzchołek jest początkowo biały, jest szary, gdy zostanie wykryty podczas wyszukiwania, i jest czarny, gdy jest zakończony, to znaczy, gdy jego lista sąsiadów została całkowicie zbadana.

Więc wszystkie wierzchołki zaczynają się na biało (nieodkryte). Kiedy węzeł zostanie wykryty, ma kolor szary (granica). Kiedy wszystko, na co wskazuje, zostało odkryte, ma kolor czarny (całkowicie wykryty). Granica to zbiór punktów, które zostały odkryte, ale mają nieodkryte dzieci.

Załóżmy, że szukasz czegoś na stronie internetowej. Najpierw przejdź do strony głównej. Załóżmy, że jest to oznaczone jako „zwierzęta”. Granicą jest obecnie {„zwierzęta”}. Przeglądasz stronę główną i nie widzisz tego, czego szukasz. Ale zauważasz, że ma linki do dwóch kolejnych stron, „poczwórnych” i „robaków”. Klikasz więc link do „poczwórnych”. Teraz granicą są {„zwierzęta”, „poczwórne”}. Przeglądasz „poczwórne” i nie znajdujesz tego, czego szukasz. Co zrobisz następnie? Możesz albo poszukać linków na „poczwórnych” i podążać za nimi, albo wrócić do „zwierząt” i kliknąć link do „robaków”. Pierwsze jest wyszukiwaniem głębokościowym, a drugie wyszukiwaniem głębokościowym.

„głębokość” odnosi się do liczby łączy z węzłem głównym, aby dostać się do węzła, natomiast „szerokość” odnosi się do węzłów o tej samej głębokości. W powyższym przykładzie BFS zaczyna się od „zwierząt” i najpierw patrzy na wszystkie węzły głębokości pierwszej, więc najpierw na „czworonogi” i „robaki”. Po obejrzeniu wszystkich węzłów głębokości 1 rozszerza granicę we wszystkich tych węzłach; to znaczy, patrzy na dzieci ze wszystkich węzłów głębokości-1, zanim spojrzy na którekolwiek z potomków węzłów głębokości-2. Na przykład, jeśli jednym z linków na stronie „czworonogów” jest „naczelne”, przejrzy wszystkie linki na stronie „robaków”, zanim spojrzy na którykolwiek z linków na stronie „naczelnych”.

$a$$a$$a$$2$$a$

W dowolnym momencie granicą fali są dokładnie te wierzchołki, które są przechowywane w strukturze danych kolejki (te wierzchołki zostały odwiedzone, ale nie zostały jeszcze zbadane).

$a$$a$

$k$$a$$k$$a$$(k \ge 0)$$0$$\{a\}$$a$$a$

$a$$a$$a$

Zatem DFS i BFS różnią się w kolejności odwiedzania wierzchołków.