Алгоритми та структури даних · Middle · Запитання 28 з 75
Чому BFS знаходить найкоротший шлях у незваженому графі?
- 1Він завжди йде ребром із найменшою вагою
- 2Він перебирає всі можливі шляхи, перш ніж вирішити
- ✓Правильна відповідь: Він відвідує вершини в порядку їхньої відстані від старту
Пояснення
Черга обробляє всі вершини на відстані 1, потім на відстані 2 і так далі. Коли BFS уперше доходить до вершини, він робить це найкоротшим шляхом. Для зважених ребер потрібен Дейкстра.