Algorithmen und Datenstrukturen · Middle · Frage 28 von 75
Warum findet BFS in einem ungewichteten Graphen den kürzesten Weg?
- 1Es folgt immer der Kante mit dem kleinsten Gewicht
- 2Es erkundet jeden möglichen Weg, bevor es entscheidet
- 3Es besucht Knoten in der Reihenfolge ihres Abstands vom Start
Antwort zeigen
Richtige Antwort: Es besucht Knoten in der Reihenfolge ihres Abstands vom Start
Erklärung
Die Queue verarbeitet alle Knoten im Abstand 1, dann im Abstand 2 und so weiter. Erreicht BFS einen Knoten zum ersten Mal, dann über einen kürzesten Weg. Bei gewichteten Kanten braucht man stattdessen Dijkstra.