я пытаюсь решить этот вопрос, но я не уверен в своем решениинеориентированный график, каково возможное минимальное остовное дерево?
Это мое решение: Я использую Kruskal алгоритм и я выбираю края, которые сделают (а) лист solution
спасибо.
Нет. Ответ будет 9. Алгоритм принимает края:
< -> Ь с 1 Стоимость: ДОБАВЛЕНО а, б теперь соединены
< -> д со стоимостью 1: ДОБАВЛЕНО а, б , d теперь подключены
b < -> d со стоимостью 4: SKIPPED
c < -> d со стоимостью 7: ADDED a, b, d, c теперь подключены, это окончательное остовное дерево.
< -> с со стоимостью 8: SKIPPED
б < -> с со стоимостью 12: SKIPPED
Таким образом, ответ 1 + 1 + 7 = 9.
но, подобно этому, узел (а) не будет листом дерева? – Manal
А, я вижу. Тогда ваш ответ правильный. Но вы не можете использовать алгоритм Kruskal, потому что он не гарантирует, что какой-либо узел будет листом в конечном остовном дереве. Алгоритм Kruskal дал бы вам ответ, который я дал, то есть 9. В таком маленьком графе вы можете легко найти все возможные связующие деревья и сравнить их. Но если вы хотите, чтобы алгоритм без грубой силы находил минимальное связующее дерево с этим дополнительным требованием, вам понадобится другой алгоритм, чем Kruskal, и я не знаю в данный момент, какой алгоритм вам нужен. –
спасибо, я нашел пример этого квестина и, как вы сказали, не нужно для Крускала. – Manal