Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 38

Рассмотрим следующий график:

Что из перечисленного НЕ является последовательностью ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Крускала?

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

Ответ: (D)
Пояснение: В последовательности (b, e) (e, f) (b, c) (a, c) (f, g) (c, d), заданной опции D, появляется ребро (a, c) веса 4 после (б, в) веса 3.

В алгоритме минимального остовного дерева Крускала мы сначала сортируем все ребра, а затем рассматриваем ребра в отсортированном порядке, так что ребро с более высоким весом не может предшествовать ребру с более низким весом.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2009 | Вопрос 38

0.00 (0%) 0 votes