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”.
