Алгоритми та структури даних · Junior · Запитання 57 з 75
Як зазвичай зберігають граф із багатьма вершинами, але небагатьма ребрами?
- 1Як матрицю n × n, заповнену нулями й одиницями
- 2Як один відсортований масив усіх вершин
- ✓Правильна відповідь: Як список суміжності: кожна вершина зі своїми сусідами
Пояснення
Список суміжності займає O(V + E) пам'яті, а матриця завжди O(V²), що марнотратно для розріджених графів. Матриця зручна для щільних графів або коли потрібна перевірка «чи є ребро?» за O(1).