Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 51

В представлении списка смежности неориентированного простого графа G = (V, E) каждое ребро (u, v) имеет две записи списка смежности: [v] в списке смежности u и [u] в списке смежности v. Они называются близнецами друг друга. Указатель-близнец — это указатель из записи списка смежности на его близнец. Если | E | = m и | V | = n, и размер памяти не является ограничением, какова временная сложность наиболее эффективного алгоритма для установки двойного указателя в каждой записи в каждом списке смежности?
(A) Θ (n 2 )
(B) Θ (m + n)
(С) Θ (м 2 )
(D) Θ (n 4 )

Ответ: (Б)
Пояснение: Сначала вам нужно найти двойников каждого узла. Вы можете сделать это, используя обход уровня порядка (т.е. BFS) один раз. Временная сложность BFS составляет Θ (m + n).
И вы должны использовать связанный список для представления, которое является дополнительным пространством (но объем памяти здесь не является ограничением).
Наконец, сложность по времени составляет Θ (m + n) для установки двойного указателя.

Вариант (B) правильный.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 51

0.00 (0%) 0 votes