Алгоритм Крускала с несвязным графом
Я не уверен, как реализовать алгоритм Крускала, когда граф имеет несколько связанных компонентов
Из моего понимания алгоритма Крускала, он многократно добавляет минимальное ребро к набору. Затем, когда все ребра проверены, он возвращает набор ребер, который дает максимум.
Однако, что если мой график отключен? Скажи, что у меня есть:
A - B - C - D
E - F
И скажем, что стоимость ( A - B) = стоимость ( E - F) = 1, а остальные края больше 1
Когда я запускаю Kruskal, я получаю все пограничные расходы, но я хочу получить стоимость КАЖДОГО подключенного компонента, поэтому я делаю в среднем минимальные затраты по всем подключенным компонентам.
0 ответов
Что ж, алгоритм Краскала работает так:
Он будет добавлять (объединять) ребра одно за другим и специализируется на поддержании непересекающихся множеств.
Похоже, вы хотите иметь минимальное связующее дерево для каждого набора связанных вершин (чтобы затем можно было поиграть с агрегированными минимальными взвешенными затратами этих отдельных деревьев), да?
Итак, вы правильно выбрали Kruskal вместо Prim (последний из которых не работает на отключенном графе).
Kruskal будет нормально работать на вашем отключенном графике; он найдет минимальное остовное дерево для каждого связного компонента.
"Для несвязных графов алгоритм Краскала возвращает лес остовных деревьев - по одному для каждого компонента графа". (отличная статья Майкла П. Фурмана - профессора кафедры компьютерных наук Эдинбургского университета о Spanning Trees)
В качестве альтернативы вы можете запускать Prim для каждого подграфа, который содержит только связанные компоненты.
Удачи (если вы еще долго не выяснили свою проблему).