Алгоритми та структури даних · Senior · Запитання 72 з 75
Яка головна причина обрати матрицю суміжності замість списків суміжності?
- 1Швидший обхід усіх сусідів
- 2Менше пам'яті на розріджених графах
- ✓Правильна відповідь: Перевірка ребра за O(1) на щільних графах
Пояснення
Перевірка matrix[u][v] миттєва, а для щільних графів пам'ять O(V²) не марнується. Для розріджених графів списки виграють і за пам'яттю, і за обходом сусідів.