Рубрики

ВОРОТА | GATE-IT-2004 | Вопрос 57

Рассмотрим неориентированный граф ниже:

Используя алгоритм Прима для построения минимального остовного дерева, начиная с узла A, какая из следующих последовательностей ребер представляет возможный порядок, в котором ребра будут добавлены для построения минимального остовного дерева?
(A) (E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
(B) (A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
(C) (A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
(D) (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)

Ответ: (D)
Объяснение: A и B неверны : идея алгоритма Прима состоит в том, чтобы построить остовное дерево — это означает, что все вершины должны быть связаны, но здесь вершины отключены

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

ВОРОТА | GATE-IT-2004 | Вопрос 57

0.00 (0%) 0 votes