Рубрики

ВОРОТА | GATE MOCK 2017 | Вопрос 21

Рассмотрим ориентированный граф с n вершинами и m ребрами, так что все ребра имеют одинаковые веса ребер. Найти сложность самого известного алгоритма для вычисления минимального остовного дерева графа?

(A) O (m + n)
(B) O (m logn)
(C) O (мн)
(D) O (n logm)

Ответ: (А)
Объяснение: Это особый случай, когда все веса ребер равны, поэтому dfs сработает, и результирующая глубина первого дерева будет остовным деревом. Таким образом, ответ будет O (m + n).

Тест на этот вопрос

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

ВОРОТА | GATE MOCK 2017 | Вопрос 21

0.00 (0%) 0 votes