Может ли алгоритм Крускала быть реализован таким образом вместо использования леса с несвязным множеством?

Question

Я изучаю MST Крускала из этой статьи geeksforgeeks .Даны следующие шаги:

1. Сортировка всех ребер в порядке убывания их веса.

2. Выберите наименьшее ребро.Проверьте, образует ли он цикл с сформированным до сих пор остовным деревом.Если цикл не сформирован, включите это ребро.Иначе, откажитесь от него.

3. Повторяйте шаг (2), пока в связующем дереве не появятся ребра (V-1).

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

Другими словами, вместо сохранения леса с непересекающимися множествами, можем ли мы просто сохранить массив битов, указывающих, какие вершины были связаны с другим ребром на каком-то предыдущем шаге?

Answer 1

Подход, который вы описываете, не будет работать должным образом во всех случаях.В качестве примера рассмотрим этот линейный график:

A - - B - - C - - D

Предположим, AB имеет вес 1, CD имеет вес 2, а B - C имеет вес 3. Что будет делать алгоритм Крускала здесь?Сначала он добавит A - B, затем C - D, а затем B - C.

Теперь представьте, что сделает ваша реализация.Когда мы добавим A - B, вы отметите A и B как посещенные.Когда мы добавим C - D, вы отметите C и D как посещенные.Но затем, когда мы пытаемся добавить B - C, так как посещаются и B, и C, вы решите не добавлять ребро, оставляя результат, который не связан.

Проблема здесь в том, что когдаПри построении MST вы можете добавить ребра, связывающие узлы, которые уже были связаны с другими узлами в прошлом.Следовательно, критерий для добавления ребра меньше: «были ли эти узлы связаны ранее?» И больше: «есть ли уже путь между этими узлами?» Вот где появляется лес с несвязным множеством.

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

Answer 2

Ваша путаница, вероятно, проистекает из шага 2, который сформулирован неверно.

В нем говорится "Проверьте, образует ли он цикл с сформированным до сих пор связующим деревом."1003 * не остовное дерево.Это лес отсоединенных остовных деревьев и некоторых не посещенных вершин.

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

Answer 3

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

Да, конечно, вы можете это сделать.Смысл использования несвязанного множества в этом алгоритме - производительность .Использование подходящей реализации несвязанного множества дает лучшую асимптотическую производительность, чем использование List.