Вступление
Одним из двух основных алгоритмов нахождения алгоритмов минимального остовного дерева является алгоритм Крускала. Прежде чем углубляться в детали, давайте вернемся к принципам минимального связующего дерева.
У нас есть взвешенный граф, и из всех остовных деревьев мы бы хотели найти тот, который имеет минимальный вес. В качестве примера на рисунке выше вы видите связующее дерево (T) на графике (G), но это не минимальное весовое остовное дерево!
Мы можем думать о группе островов и возможных связях мостов, соединяющих их. Конечно, строительство мостов стоит дорого и занимает много времени, поэтому мы должны знать, какие мосты мы хотим построить. Тем не менее, есть важный вопрос, какую минимальную цену мы хотели бы заплатить, чтобы построить такой набор мостов, соединяющих все острова.
Таким образом, нам практически необходимо построить минимальное остовное дерево, где вершинами будут острова, а ребрами будут возможные мосты между ними. У каждого возможного моста есть вес (цена или время, которое мы должны построить, и т. Д.).
Этот сценарий является лишь одним из возможных случаев использования минимальных остовных деревьев на практике.
Однако два основных подхода — алгоритмы Крускала и Прима — отличаются.
обзор
Алгоритм Крускала начинается с инициализации набора | V | деревья.
В процессе построения окончательного остовного дерева мы сохраняем лес. Очевидно, мы начнем с леса с | V | деревья, где каждое дерево является одним узлом дерева.
В какой-то момент у нас есть лес «k» деревьев, которые являются поддеревьями минимального остовного дерева.
Наконец, за один шаг до построения окончательного MST у нас есть два дерева, и мы связываем их с менее взвешенным ребром слева, который соединяет их.
Важно отметить, что в процессе построения дерева мы сортируем ребра в порядке возрастания по их весу.
Затем мы начинаем получать ребра и проверяем, принадлежат ли их концы (две вершины, составляющие ребро) разным поддеревьям.
Псевдокод
1. T (the final spanning tree) is defined to be the empty set;
2. For each vertex v of G, make the empty set out of v;
3. Sort the edges of G in ascending (non-decreasing) order;
4. For each edge (u, v) from the sored list of step 3.
If u and v belong to different sets
Add (u,v) to T;
Get together u and v in one single set;
5. Return T
Отличительной особенностью алгоритма Крускала является то, что он также работает на несвязных графах.
история
Алгоритм Крускала назван в честь Джозефа Крускала , который был не только ученым, но и выдающимся математиком и статистиком. Хотя он наиболее известен своим алгоритмом вычисления минимального остовного дерева, описанным в этом посте, он также известен своей работой статистика и своим вкладом в формулировку многомерного масштабирования.
Крускал также исследовал индоевропейские языки, способствуя изучению лингвистики вместе с другими учеными. Его «Индоевропейский лексикографический список» (http://www.wordgumbo.com/ie/cmp/) до сих пор широко используется.