Kann jemand die Breitensuche erklären?

Question

Kann jemand Breitensuche erklären die unten Art von Problemen

Ich brauche zu lösen alle Wege zwischen 4 und 7

Answer 1

Sie auf allen Knoten aussehen finden neben Ihrem Startknoten. Dann sehen Sie sich alle Knoten an, die an diese Knoten angrenzen (Sie kehren nicht zu Knoten zurück, die Sie bereits angesehen haben). Wiederholen Sie dies, bis der befriedigende Knoten gefunden wurde oder keine Knoten mehr vorhanden sind.

Für die Art von Problem, das Sie angeben, verwenden Sie den oben beschriebenen Prozess, um eine Reihe von Pfaden zu erstellen, die alle enden, die am gewünschten Zielknoten ankommen, und wenn Ihr Diagramm erschöpft ist, ist die Menge der Pfade so beendet Ihre Lösungsmenge.

Answer 2

Sie testen jeden Knoten, der mit dem Stammknoten verbunden ist. Dann testen Sie jeden Knoten, der mit den vorherigen Knoten verbunden ist. Also weiter, bis du deine Antwort gefunden hast.

Grundsätzlich testet jede Iteration Knoten, die die gleiche Entfernung vom Stammknoten entfernt sind.

Answer 3

Breite erste Suche (BFS) bedeutet, dass Sie alle direkten Kinder Ihrer Startknoten verarbeiten, bevor Sie in tiefere Ebenen gehen. BFS wird mit einer Warteschlange implementiert, die eine Liste von Knoten speichert, die verarbeitet werden müssen.

Sie starten den Algorithmus, indem Sie Ihren Startknoten zur Warteschlange hinzufügen. Dann führen Sie Ihren Algorithmus so lange aus, bis Sie nichts mehr in der Warteschlange verarbeiten können.

Wenn Sie ein Element aus der Warteschlange entfernen, wird es zu Ihrem aktiven Knoten. Wenn Sie Ihren aktiven Knoten verarbeiten, fügen Sie alle seine untergeordneten Elemente der Rückseite der Warteschlange hinzu. Sie beenden den Algorithmus, wenn Sie eine leere Warteschlange haben.

Da es sich um ein Diagramm anstelle eines Baums handelt, müssen Sie eine Liste Ihrer verarbeiteten Knoten speichern, damit Sie nicht in eine Schleife einsteigen.

Sobald Sie Knoten 7 erreichen, haben Sie einen passenden Pfad und Sie können aufhören, die BFS für diesen rekursiven Pfad zu tun. Das bedeutet, dass Sie seine untergeordneten Elemente einfach nicht zur Warteschlange hinzufügen. Um Schleifen zu vermeiden und den genauen Pfad zu kennen, den Sie besucht haben, übergeben Sie bei der Ausführung rekursiver BFS-Aufrufe die bereits besuchten Knoten.

Answer 4

BEGINN

4;

4,2;

4,2,1; 4,2,3; 4,2,5;

4,2,1; (nicht bestanden) 4,2,3,6; 4,2,5,6; 4,2,5,11;

4,2,3,6,7; (bestanden) 4,2,3,6,8; 4,2,5,6,7, (Pass) 4,2,5,6,8; 4,2,5,11,12;

4,2,3,6,8,9; 4,2,3,6,8,10; 4,2,5,6,8,9; 4,2,5,6,8,10; 4,2,2,11,12; (nicht bestanden)

4,2,3,6,8,9; (nicht bestanden) 4,2,3,6,8,10; (nicht bestanden) 4,2 (gescheitert) 4,2,5,6,8,10;;, 5,6,8,9 (gescheitert)

END

Answer 5

Betrachten sie es als Webseiten mit Links zu anderen Seiten auf sie. Sei A unser Wurzelknoten oder unsere Startseite.

 
A is the starting page (Layer 1) 
A links to AA, AB, AC  (Layer 2) 
AA links to AAA, AAB, AAC (Layer 3) 
AB links to ABA, ABB, ABC (Layer 3) 
AC links to ACA, ACB, ACC (Layer 3) 

Dies ist nur drei Schichten tief. Sie durchsuchen jeweils eine Ebene. In diesem Fall würden Sie also bei Schicht A beginnen. Wenn das nicht stimmt, gehen Sie zur nächsten Schicht, AA, AB und AC. Wenn keine dieser Websites die von Ihnen gesuchte ist, folgen Sie den Links und gehen Sie zur nächsten Ebene. Mit anderen Worten, Sie sehen sich jeweils eine Ebene an.

Eine tiefe erste Suche (ihr Komplement) würden Sie von A zu AA zu AAA gehen. Mit anderen Worten, Sie würden DEEP gehen, bevor Sie WIDE gehen.