Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 43

Для неориентированного взвешенного графа, приведенного ниже, какая из следующих последовательностей ребер представляет собой правильное выполнение алгоритма Прима для построения минимального остовного дерева?

(A) (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)
(B) (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)
(C) (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)
(D) (h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

Ответ: (с)
Объяснение: В алгоритме простых чисел мы начинаем с любого узла и продолжаем исследовать соседние узлы с минимальной стоимостью, которые уже покрыты.
Тест на этот вопрос

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

ВОРОТА | Gate IT 2008 | Вопрос 43

0.00 (0%) 0 votes