Алгоритм Краскала

Существует несколько алгоритмов, которые позволяют находить минимальное остовное дерево в заданном связном неориентированном графе G = (V, E). Наиболее

эффективным из них является Алгоритм Краскала [1]:

1. На каждом шаге поддерживается набор ребер минимального остова E. В самом начале оно является пустым, E = ∅.

2. Выберем еще не рассмотренное ребро (u, v) ∈ E, причем минимального веса.

3. Если все ребра рассмотрены, то алгоритм завершен, а граф G = (V, E), является минимальным остовным деревом графа G = (V, E). Иначе выполнение с шага 2.

Рассмотрим подробнее шаг 3, а точнее, проверку на образование цикла. Для того

чтобы упростить задачу, будем поддерживать множество T непересекающихся подмножеств множества вершин V в графе.

В начале, предположим, что T = {G1, G2,..., G|V | }, где Gk = {k}. Проще говоря,

каждая вершина в самом начале входит в свое собственное подмножество. Теперь рассмотрим заново шаг 3 алгоритма, c учетом наличия этого множества:

• Если вершины u и v принадлежат различным множествам из T, то это значит, что было найдено ребро минимального веса, соединяющее два подмножества (компоненты связности) в одно.

Объединим эти два множества в одно, и добавим рассматриваемое ребро (u, v)

к множеству E.

Если вершины u и v принадлежат одному и тому же множеству из T, то такое

ребро пропускается, так как при его добавлении образуется цикл.

Дата добавления: 2015-08-18