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

 

Содержание:

 

 

1. Введение.
2. Нахождение кратчайших путей в графе.
3. Описание алгоритма Краскала.
4. Псевдокод алгоритма.
5. Блок-схема алгоритма.
6. Оценка сложности алгоритма и пример.
7. Вывод.
8. Список использованной литературы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение.

 

Граф - Пара объектов G = (X , Г), где Х - конечное множество,

а  Г – конечное подмножество  прямого произведения  Х*Х.  При этом  Х называется множеством вершин, а Г - множеством дуг графа G .

Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ ÍV и множеством ребер (дуг) E₁Í E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

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

Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую, ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.

Алгоритм Краскала (или алгоритм Крускала) - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Алгоритм Краскала может  строить дерево одновременно для  нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

Полный граф задается списком ребер. Перед работой  список ребер сортируется по возрастанию длины. На каждом шаге просматривается список ребер, начиная с ребра, следующего за вошедшим в решение на предыдущем шаге, и к строящемуся поддереву присоединяют то ребро, которое не образует цикла с ребрами, уже включенными в решение.

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной. На практике алгоритм Краскалы применятся в работе авиалиний при нахождении наименьшего воздушного пути из одного пункта назначения в другой.

 

 

 

 

 

 

 

2. Нахождение кратчайших путей в графе.

 

Начальные понятия

 

Будем рассматривать  ориентированные графы G = <V, E>, дугам которых приписаны веса. Это означает, что каждой дуге <u, v> ÎE поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Полагаем, кроме того, a (u, v) = ╔ , если u -a v.

Нас будет интересовать нахождение кратчайшего пути между  фиксированными вершинами s, t ÎV. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = ╔ . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v₁,..., v_p не будет повторов.

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

 

Алгоритм нахождения кратчайшего пути

 

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v Î V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v ÎV.

Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.

Пусть <V, E> -ориентированный граф, | V|  = n, | E|  = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(n²). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u (r) v, то в этом случае сложность будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем пути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {u, v}двумя дугами á u, vñ и áv, uñ , каждая с таким же весом, что и {u, v}. Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E> является ориентированным графом, |V|  = n, |E|  = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых «большинство» вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A[u, v], u, vÎ V (A[u, v] содержит вес a (u, v)).

 

3. Описание алгоритма Краскала.

 

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

 

Алгоритм состоит из следующей последовательности действий:

 

1. Создается список ребер E, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево.

 

2. Данный список упорядочивается в порядке возрастания длин ребер.

 

3. Просматривается список E и выбирается из него ребро с максимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.

 

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

 

 

 

 

 

 

4. Псевдокод алгоритма.

 

Отсортировать ребра  в порядке возрастания весов инициализировать структуру разбиений

 

edgeCount=l

while edgeCount <= E and includedCount <= М-l do

parentl = FindRoot (edge [edgeCount]. start)

parent2 = FindRoot (edge [edgeCount]. end)

if parentl != parent2 then

добавить edge [edgeCount] в остовное дерево

includedCount = includedCount = l

Union (parent1,parent2)

end if

edgeCount=edgeCount+l

end while.

 

E - число ребер в графе;

V - число вершин в графе

edgeCount - переменная;

includedCount - переменная;

Parent - массив, в котором  под каждый элемент множества,  с которым мы собираемся работать, отведена одна ячейка;

FindRoot (x) - (x элемент, для которого мы хотим найти корень части, его содержащей) процедура, начинающая с ячейки Parent [x], в которой хранится номер непосредственного предка элемента x;

Union - функция, выполняющая  объединение двух частей в  одну.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Блок-схема алгоритма.

 

Рис. 1. Общая схема.

Рис. 2. Блок-схема алгоритма сортировки вставками.

Рисунок 3 - Блок-схема алгоритма Краскала

6. Сложность алгоритма.

 

Сложность этого алгоритма  совпадает со сложностью используемого  алгоритма сортировки, поскольку  число операций в цикле while линейно  по числу ребер. Поэтому сложность  алгоритма Крускала поиска МОД равна O(Elog Е).

 

 

Пример

Изображение	Описание
	Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро AD (выделено на рисунке).
	Теперь наименьший вес, равный 5, имеет ребро CE. Так добавление CE не образует цикла, то выбираем его в качестве второго ребра.
	Аналогично выбираем ребро DF, вес которого равен 6.
	Следующие ребра  — AB и BE с весом 7. Произвольно выбирается ребро AB, выделенное на рисунке. Ребро BD выделено красным, так уже существует путь (зеленый) между B и D, поэтому, если бы это ребро было выбрано, то образовался бы цикл ABD.
	Аналогичным образом  выбирается ребро BE, вес которого равен 7. На этом этапе красным выделено гораздо больше ребер: BC, потому что оно создаст цикл BCE, DE, потому что оно создаст цикл DEBA, и FE, потому что оно сформирует цикл FEBAD.
	Алгоритм завершается добавлением ребра EG с весом 9.Минимальное остовное дерево построено.

 

 

7. Вывод.

 

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

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

 

 

 

 

 

 

 

 

 

 

8. Список использованной литературы.

 

1. Свободная энциклопедия ВикипедиЯ [Электронный ресурс]. - Режим доступа: http://ru. wikipedia.org/.

2. Макконелл Дж. Основы современных алгоритмов: 2-е дополненное издание М.: Техносфера, 2004. - 368с. ISBN 5-94836-005-9.

3.   [Электронный ресурс] http://www.lotos-khv. narod.ru/.

4.   Новиков Ф.А. Дискретная математика для программистов. 2008. с. 327-330