Алгоритми та структури даних · Middle · Запитання 60 з 75
Яка складність BFS чи DFS на графі, збереженому списками суміжності?
- 1O(V × E)
- ✓Правильна відповідь: O(V + E)
- 3O(V²) у будь-якому разі
Пояснення
Кожну вершину обробляють один раз, і кожне ребро переглядають один раз (двічі для неорієнтованих графів). З матрицею суміжності той самий обхід коштує O(V²), бо кожен рядок має V клітинок.