Алгоритм теории графов для минимально соединяющих областей с общими границами

Question

У меня есть взвешенный график из нескольких «ручек для животных», каждая из которых имеет как минимум 3 ребра / точки и как минимум две ручки. Я должен выяснить минимальные взвешенные края, которые нужно удалить, чтобы соединить все ручки (Вы можете соединить их, удалив внешние края, не связанные с другими ручками тоже).

Может кто-нибудь порекомендовать алгоритм или процесс, с помощью которого я мог бы подойти к поиску минимально взвешенных стенок для удаления. Я думал об алгоритме Прима, но я даже не совсем уверен, как можно это применить.

Это проблема S4 на http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

Я не хочу получить ответ, просто указание, как к нему подойти

Answer 1

Вы находитесь в правильном направлении.

Смоделируйте вашу проблему как неориентированный граф G=(V,E), где V = { all pens }, E = { (u,v) | there is a wall between u and v } с w((u,v)) = cost of wall between u and v

Для того, чтобы «соединить все ручки» - вы на самом деле ищете подграф: G'=(V,E') такой, что будет подключен подграф G' [Существует путь между каждыми двумя узлами], и стоимость стен в Е 'минимальны.

Чтобы получить это при минимальных затратах - вы ищете Минимальное связующее дерево . [Легко видеть, что вам действительно нужно дерево - потому что любое дополнительное ребро после создания дерева является избыточным и может быть удалено без ущерба для связности графа - или, в терминах задачи - вы можете восстановить одну стену, и ручки будут оставайтесь на связи]

Два возможных алгоритма, которые помогут вам получить MST: Prim и Kruskal