0 Daumen
3k Aufrufe

Ich habe keine Ahnung wie man einen BFS-Baum zeichnet. Was wird der Unterschied zur vorgegebenen Graf? Hab ein Beispiel im Inet gefunden, aber da wurde nicht erklärt wie man das macht und warum sind einige Kanten entfernt. Kann mir bitte jemand erklären?

blob.png

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

Bei Wikipedia steht das:

Zuerst wird ein Startknoten u  ausgewählt. Von diesem Knoten aus wird nun jede Kante ( u , v ) betrachtet und getestet, ob der gegenüberliegende Knoten v  schon entdeckt wurde bzw. das gesuchte Element ist.

Ist dies noch nicht der Fall, so wird der entsprechende Knoten in einer Warteschlange gespeichert und im nächsten Schritt bearbeitet. Hierbei ist zu beachten, dass Breitensuche immer zuerst alle direkt nachfolgenden Knoten bearbeitet, und nicht wie die Tiefensuche einem Pfad in die Tiefe folgt.

Nachdem alle Kanten des Ausgangsknotens betrachtet wurden, wird der erste Knoten der Warteschlange entnommen und das Verfahren wiederholt.

Bei deinem Beispiel heißt das: Die Warteschlange sieht nach dem Besuch jedes Folgeknotens des

Startknotens so  aus:

5    7   
Dann geht es also bei 5 weiter und weil dem nichts Neues mehr folgt, kommt auch nichts mehr in die Schlange.

Also ist dort nur noch 7 und bei der 7 kommen dann 4 und 3 in die Schlange

4  3 

von 4 aus gibt es nichts Neues und von 3 aus auch nicht. Also ist nach dem Anhängen dieser 

beiden Ästen die Schlange leer, der Baum fertig.

Avatar von 287 k 🚀

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
1 Antwort
1 Antwort
Gefragt 13 Jul 2016 von akaike
1 Antwort
Gefragt 29 Aug 2023 von eli-98

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community