Алгоритми та структури даних · Middle · Запитання 29 з 75
Навіщо обходам графа множина visited?
- 1Щоб тримати вершини відсортованими під час обходу
- ✓Правильна відповідь: Щоб не обробляти вершини двічі й не зациклюватися на циклах
- 3Щоб зберігати остаточну відповідь алгоритму
Пояснення
На відміну від дерев, графи можуть мати цикли й кілька шляхів до тієї самої вершини. Без visited обхід може відвідувати вершини нескінченно; з нею кожна вершина обробляється один раз, O(V + E).