Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 90

Каков вес минимального остовного дерева следующего графика?


(А) 29
(Б) 31
(С) 38
(D) 41

Ответ: (Б)
Объяснение: (a, c), (a, d), (d, b), (b, g), (g, h), (h, f), (h, i), (i, j), (я, е) = 31

Требуется фон — Минимальное остовное дерево ( Примы / Крускал )

В таких вопросах всегда используйте алгоритм kruskal, чтобы найти минимальное связующее дерево, так как оно легко и меньше шансов сделать глупые ошибки.

Алгоритм:

Всегда выбирайте минимальный вес ребра и попробуйте добавить в текущий лес (Коллекция деревьев), если цикл не сформирован, иначе отбросьте.
Как только вы добавили n-1 ребер в лес, остановитесь, и вы получите минимальное остовное дерево.

Смотрите изображение ниже для построения MST этого вопроса.

Вес минимального остовного дерева = сумма всех ребер в минимальном остовном дереве
= 31

Это объяснение было предоставлено Пранджул Ахаджа.

Посетите следующие ссылки, чтобы узнать больше:
http://www.ics.uci.edu/~eppstein/161/960206.html
https://en.wikipedia.org/wiki/Minimum_spanning_tree

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

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

ВОРОТА | GATE-CS-2003 | Вопрос 90

0.00 (0%) 0 votes