Алгоритм Крускала с несвязным графом

Я не уверен, как реализовать алгоритм Крускала, когда граф имеет несколько связанных компонентов.

Насколько я понимаю алгоритм Крускала, он постоянно добавляет к набору минимальное ребро. Затем, когда все ребра проверены, он возвращает набор ребер, который дает больше всего.

Однако что, если мой график отключен? Скажем, у меня есть:

A - B - C - D

E - F

И скажем, стоимость ( A - B ) = стоимость ( E - F ) = 1, а остальные ребра больше 1

Когда я запускаю Kruskal, я получаю все затраты на ребро, но я хочу получить стоимость КАЖДОГО подключенного компонента, поэтому я вычисляю среднюю минимальную стоимость по всем подключенным компонентам.


graph algorithm minimum-spanning-tree kruskals-algorithm
person Jack    schedule 07.03.2014    source источник
comment
Как это вопрос программирования? Возможно, вам повезет больше на другом сайте StackExchange.   -  person Madbreaks    schedule 07.03.2014
comment
Kruskal даст вам минимальный связующий лес. Если вам нужна стоимость одного дерева в этом лесу, просто сложите ее. В чем проблема?   -  person Beta    schedule 07.03.2014
comment
Мне нужно взять среднее значение каждого леса.   -  person Jack    schedule 07.03.2014
comment
Ваш язык неясен. Предположим, что cost(B-C) равно 2, а cost(C-D) равно 6. Теперь покажите нам, что вы хотите вычислить.   -  person Beta    schedule 07.03.2014
comment
В этом случае Kruskal's даст вам минимальный связующий лес. Просто найдите подключенные компоненты до или после запуска Kruskal, это не имеет значения.   -  person Niklas B.    schedule 07.03.2014

Ответы (1)


arrow_upward
0
arrow_downward

Итак, алгоритм Крускала работает так:

Он будет добавлять (объединять) ребра одно за другим и специализируется на поддержании непересекающихся наборов.

Похоже, вы хотите иметь минимальное остовное дерево для каждого набора связанных вершин (чтобы затем вы могли поиграть с агрегированными минимальными взвешенными затратами этих отдельных деревьев) , да?

Итак, вы правы, выбрав Крускала, а не Прима (последний из которых не будет работать на отключенном графе).

Kruskal будет нормально работать на вашем отключенном графе; он найдет минимальное остовное дерево для каждого подключенного компонента.

«Для несвязанных графов алгоритм Крускала возвращает лес остовных деревьев — по одному для каждого компонента графа». (отличная статья Майкла П. Фурмана о связующих деревьях) — профессор компьютерных наук Эдинбургского университета)

В качестве альтернативы вы можете запустить Prim на каждом подграфе, который содержит только подключенные компоненты.

Удачи (если вы еще долго не разобрались со своей проблемой).

Псевдокод алгоритма Крускала

person Wilson Huang    schedule 20.04.2020