Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 20

Пусть G граф с n вершинами и m ребрами. Какова самая тесная верхняя граница времени бега при первом поиске глубины G? Предположим, что граф представлен с использованием матрицы смежности.
(A) O (n)
(B) O (m + n)
(С) O (n 2 )
(D) O (мн)

Ответ: (с)
Объяснение: Поиск в глубине Поиск графика занимает O (m + n) время, когда график представлен с использованием списка смежности.

В представлении матрицы смежности граф представлен в виде матрицы «nxn». Чтобы выполнить DFS, для каждой вершины мы проходим строку, соответствующую этой вершине, чтобы найти все смежные вершины (в представлении списка смежности мы проходим только смежные вершины вершины). Следовательно, временная сложность становится O (n 2 )
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 20

0.00 (0%) 0 votes