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

Построения минимального остовного дерева (Алгоритм Краскала)

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

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

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

1. Сортируем ребра графа по возрастанию весов.

2. Полагаем, что каждая вершина относится к своей компоненте связности.

3. Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем:

Если вершины, соединяемые данным ребром, лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву.

Если вершины, соединяемые данным ребром, лежат в одной компоненте связности, то исключаем ребро из рассмотрения.

4. Если есть еще нерассмотренные ребра и не все компоненты связности

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

языков, то будем работать с простыми массивами. Для задания набора ребер используем два массива E: array [1..m,1..2] of integer - здесь m - количество ребер

m<n2-n+1, где n - количество вершин, и массив EW: array [1..m] of real, тогда ребро ei, соединяющее вершины u, v с весом wi будет соответствовать элементам E[i,1]=u, E[i,2]=v, EW[i]=w. Таким образом, до начала непосредственно поиска минимального остовного дерева нам необходимо пройти матрицу весов W и заполнить массивы E и EW.

Преобразовав представление графа от весовой матрицы к набору ребер (часто граф изначально задается при помощи списка ребер, и тогда предыдущая часть алгоритма становится не нужна), мы уже можем легко упорядочить ребра по неубыванию весов, я для этого использую в блок-схеме алгоритм пузырька, чтобы не "замазывать" основной алгоритм, но можно легко перейти и к другим способам упорядочивания. Далее в алгоритме вводиться массив V: array [1..n] of integer элементы, которого характеризуют номер компоненты связности соответствующих вершин (две вершины u1,u2 лежат в одной компоненте связности, если и только если V[u1]=V[u2]). Теперь все структуры используемые в алгоритме описаны, и его работу легко будет понять из блок-схемы.

В заключении еще только одно замечание. В алгоритме используется переменная q, которая инициализируется значением n-1(на единицу меньше числа вершин) и затем, при объединении двух компонент связности на шаге 3, q уменьшается на единицу, таким образом, когда (если) q на некотором шаге занулится, то это будет означать, что все вершины лежат в одной компоненте связности и работа алгоритма завершена.

Найденное дерево будет определено с помощью массива WO - матрицы весов.

93