Выбор ответа Junior Графы: BFS и DFS обновлено
Представление графа
Вопрос
Граф из 10⁵ вершин и 2·10⁵ рёбер. Как его хранить?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Список смежности: массив массивов соседей. Список смежности занимает O(V + E) и даёт соседей вершины напрямую.
Варианты ответа
- Матрица смежности 10⁵ × 10⁵ из битов
- Массив рёбер и поиск соседей перебором
- Список смежности: массив массивов соседейправильный ответ
- Строка JSON с рёбрами, парсить по запросу
Разбор
Список смежности занимает O(V + E) и даёт соседей вершины напрямую. Это стандарт для разреженных графов.
- Матрица займёт 10¹⁰ ячеек: столько памяти нет.
- Перебор массива рёбер для каждой вершины даст O(V · E).
- JSON-строка не структура данных для обхода.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.