Was bedeutet "Breite" bei der Breitensuche?

Ich lernte etwas über die Breitensuche und kam mir die Frage, warum BFS so heißt. In dem Buch Einführung in Algorithmen von CLRS habe ich den folgenden Grund dafür gelesen:

Die Breitensuche wird so genannt, weil sie die Grenze zwischen entdeckten und unentdeckten Eckpunkten gleichmäßig über die Breite der Grenze erweitert.

Ich kann die Bedeutung dieser Aussage jedoch nicht verstehen. Ich bin verwirrt über dieses Wort "Grenze" und die Breite dieser Grenze.

Kann jemand diese Frage bitte auf eine Weise beantworten, die für einen Anfänger wie mich leicht zu verstehen ist?

Betrachten Sie die Datenstruktur, die zur Darstellung der Suche verwendet wird. In einem BFS verwenden Sie eine Warteschlange. Wenn Sie auf einen unsichtbaren Knoten stoßen, fügen Sie ihn der Warteschlange hinzu.

Die "Grenze" ist die Menge aller Knoten in der Suchdatenstruktur. Die Warteschlange durchläuft nacheinander alle Knoten an der Grenze und iteriert so über die Breite der Grenze. Die DFS wird immer den zuletzt entdeckten Status vom Stapel entfernen und somit immer über den tiefsten Teil der Grenze iterieren .

Betrachten Sie das Bild unten. Beachten Sie, wie die DFS direkt zu den tiefsten Teilen des Baums gelangt, während die BFS über die Breite jeder Ebene iteriert.

Bild hier

Das Zitat, das Sie geben, sagt "die Grenze zwischen entdeckten und unentdeckten Eckpunkten". Das ist also die Grenze, von der der Autor spricht: die Grenze zwischen entdeckten und unentdeckten Eckpunkten. Sie haben einige Eckpunkte, die Sie noch gar nicht gesehen haben. Sie haben auch einige Eckpunkte, für die Sie alles gesehen haben. Und dann haben Sie Eckpunkte dazwischen. Dies sind Eckpunkte, die Sie sich angesehen haben, aber Sie haben noch nicht alle ihre Kinder geladen. Dies ist die Grenze.

Der diskutiert dies weiter auf:

Um den Fortschritt zu verfolgen, färbt BFS jeden Scheitelpunkt weiß, grau oder schwarz. Alle Eckpunkte beginnen weiß und können später grau und dann schwarz werden. Der Scheitelpunkt wird entdeckt, wenn er zum ersten Mal während der Suche angetroffen wird. Zu diesem Zeitpunkt wird er nicht mehr weiß. Es wurden daher graue und schwarze Eckpunkte entdeckt, aber BFS unterscheidet zwischen ihnen, um sicherzustellen, dass die Suche auf BF-Weise fortgesetzt wird.
...
jeder Scheitelpunkt ist anfangs weiß, grau, wenn er bei der Suche entdeckt wird, und schwarz, wenn er fertig ist, dh wenn seine Adjazenzliste vollständig untersucht wurde.

Alle Eckpunkte beginnen also weiß (unentdeckt). Wenn ein Knoten entdeckt wird, ist er grau (Grenze). Wenn alles entdeckt wurde, worauf es hinweist, ist es schwarz gefärbt (vollständig entdeckt). Die Grenze ist die Menge der Punkte, die entdeckt wurden, aber unentdeckte Kinder haben.

Angenommen, Sie suchen etwas auf der Website. Sie gehen zuerst zur Hauptseite. Angenommen, das ist mit "Tiere" gekennzeichnet. Die Grenze ist derzeit {"Tiere"}. Sie schauen durch die Hauptseite und sehen nicht, wonach Sie suchen. Sie bemerken jedoch, dass es Links zu zwei weiteren Seiten gibt, "Vierbeiner" und "Würmer". Sie klicken also auf den Link zu "Vierbeiner". Jetzt ist die Grenze {"Tiere", "Vierbeiner"}. Sie schauen durch "Vierbeiner" und finden nicht, wonach Sie suchen. Was machst du als nächstes? Sie können entweder nach Links zu "Vierbeinern" suchen und diesen folgen oder zu "Tiere" zurückkehren und auf den Link zu "Würmer" klicken. Die erste ist eine Tiefensuche, und die zweite ist eine Breitensuche.

"Tiefe" bezieht sich auf die Anzahl der Links vom Stammknoten, die erforderlich sind, um zu einem Knoten zu gelangen, während "Breite" sich auf Knoten mit derselben Tiefe bezieht. Im obigen Beispiel beginnt BFS bei "Tieren" und betrachtet zuerst alle Knoten der Tiefe Eins, also zuerst "Vierbeiner" und "Würmer". Nachdem es alle Knoten der Tiefe 1 betrachtet hat, erweitert es die Grenze über alle diese Knoten; Das heißt, es werden die untergeordneten Elemente aller Knoten der Tiefe 1 betrachtet, bevor eines der untergeordneten Elemente der Knoten der Tiefe 2 betrachtet wird. Wenn beispielsweise einer der Links auf der Seite "Vierbeiner" "Primaten" ist, werden alle Links auf der Seite "Würmer" angezeigt, bevor die Links auf der Seite "Primaten" angezeigt werden.

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

Zu jedem Zeitpunkt sind die Grenzen der Welle genau die Eckpunkte, die in der Warteschlangendatenstruktur gespeichert sind (diese Eckpunkte wurden besucht, aber noch nicht weiter untersucht).

$a$$a$

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

$a$$a$$a$

Daher unterscheiden sich DFS und BFS in der Reihenfolge, in der sie die Eckpunkte besuchen.