Содержание
Введение
1. Постановка задачи
2. Методы решения данной проблемы
3. Описание алгоритма Краскала
4. Пример работы алгоритма Краскала
5. Код программы
6. Обзорработы программы
Заключение
Список использованной литературы
Введение
Минимальным остовным деревом (МОД) связного взвешенного графаназывается его связный подграф, состоящий из всех вершин исходного дерева и некоторыхего ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен,то описываемую ниже процедуру можно применять поочередно к каждой его компонентесвязности, получая тем самым минимальные остовные деревья для этих компонент.
Задача о нахождении минимального остовного дерева часто встречаетсяв подобной постановке: есть n городов, через которые можно проложить маршруттак, чтобы можно было добраться из любого города в любой другой (напрямую или черездругие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.
Эта задача можетбыть сформулирована в терминах теории графов как задача о нахождении минимальногоостовного дерева в графе, вершины которого представляют города, рёбра — это парыгородов, между которыми есть маршрут, а вес ребра равен стоимости проезда по соответствующемумаршруту.
Существует несколькоалгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известныеиз них перечислены ниже:
· АлгоритмПрима;
· АлгоритмКраскала;
· АлгоритмБорувки.
1. Постановка задачи
Пусть имеется связный неориентированный граф G, на ребрах которогозадана весовая функция c (e). Связный подграф графа G, являющийся деревом и содержащийвсе его вершины, называют покрывающим деревом (spanning-tree) этого графа (иногдаиспользуют термин остовное дерево или остов). Весом остовного дерева будем считатьсумму весов всех его ребер. Тогда возникает задача о нахождении максимального покрывающегодерева, т.е. такого, что его вес наибольший, либо равен весу любого из покрывающихдеревьев для данного графа. Будем обозначать наибольшее покрывающее дерево графаG как MAX (G).
2. Методы решения данной проблемы
Остовным деревомграфа называется дерево, содержащее все вершмины V графа. Стоимость остовного деревавычисляется как сумма стоимостей всех ребер.
Идея решения:
Для остовногодерева верно следующее свойство:
Пусть G= (V,E)- свызный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначимчерез U подмножество множества вершин V. Если (u,v) — такое ребро наибольшей стоимости,что u из U и v из V\U, тогда для графа G существует остовное дерево максимальнойстоимости, содержащее ребро (u,v)
На этом свойствеоснован алгоритм Прима. В этом алгоритме строится множество вершин U, из которого«вырастает» остовное дерево. Пусть V={1,2,. n}. Сначала U={1}. На каждомшаге алгоритма находится ребро наименьшей стоимости (u,v) такое, что u из U и vиз V\U, затем вершина v переносится из множества V\U в множество U. Процесс продолжаетсядо тех пор, пока множество U не станет равным множеству V.
Детали реализации:
Удобно выбратьпредставление в виде списка дуг.
Допустим, необходимопроложить кабель по территории университета, связав все его здания, так, чтобы изкаждого здания кабель по какому-либо пути доходил до любого другого здания. Крометого, предположим, что надо минимизировать общую длину прокладываемого кабеля. Еслирассматривать здания как вершины, а кабели между зданиями как ребра, то эта работас прокладыванием кабеля превращается в задачу определения каркаса, охватывающегоздания территории университета, в котором общая длина проложенного кабеля должнабыть минимальной. Такую задачу называют нахождением каркаса минимального веса. Внашей работе длина проложенного кабеля должна быть максимальной.
Определим понятиекаркаса более формально. Если дан связный неориентированный граф G= (V, E), то каркас(также называемый остовным или стягивающим деревом) T= (V, E’), где E’ÍE — это связный граф без циклов.Иными словами, каркас неориентированного графа G — это подграф графа G, дерево,содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же наборвершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно|V|-1 ребро.
Предположим, чтодля каждого ребра eÎE существует вес w (e), причем такой вес может выражать,например, цену, длину или время, необходимое для прохода по ребру (в нашем примере- длину кабеля между зданиями). Во взвешенном графе вес подграфа — это сумма весовего ребер. Тогда каркас T максимального веса — это каркас G, в котором вес деревамаксимален относительно всех остовных деревьев G.
Если граф G несвязный,он не может иметь остовного дерева, но у него есть остовный лес. Также можно изменитьалгоритм нахождения остовного дерева максимального веса, чтобы на выходе получатьминимальный остовный лес.
остовное дерево алгоритм краскал
В алгоритме Краскалаиспользуется жадный подход к решению задачи, т.е. в любой момент выполнения данныхалгоритмов существует множество ребер E’, представляющее подмножество некоторогоминимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребервыбирается «лучшее» ребро, обладающее определенными свойствами, и добавляетсяк формируемому каркасу максимального веса. Одним из важных свойств любого ребра,добавляемого к E’, является его безопасность, т.е. то, что обновленное множестворебер E’ будет продолжать представлять подмножество некоторого минимального остовногодерева.
3. Описание алгоритма Краскала
Алгоритм Краскала может строить дерево одновременно для несколькихкомпонент связности, которые в процессе решения объединяются в одно связанное дерево.
Полный граф задается списком ребер. Перед работой список реберсортируется по возрастанию длины. На каждом шаге просматривается список ребер, начинаяс ребра, следующего за вошедшим в решение на предыдущем шаге, и к строящемуся поддеревуприсоединяют то ребро, которое не образует цикла с ребрами, уже включенными в решение.
Алгоритм состоит из следующей последовательности действий:
1. Создается список ребер R, содержащий длину ребра, номер исходной вершиныребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево.
2. Данный список упорядочивается в порядке возрастания длин ребер.
3. Просматривается список R и выбирается из него ребро с максимальной длиной,еще не включенное в результирующее дерево и не образующее цикла с уже построеннымиребрами.
4. Если все вершины включены в дерево и количество ребер на единицу меньше количествавершин, то алгоритм свою работу закончил. В противном случае осуществляется возвратк пункту 3.
Или в терминах теории графов:
Дан граф с n вершинами;длины ребер заданы матрицей. Найти остовное дерево максимальной длины.
В задаче Прима-Краскала,которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.
Как известно(это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждоеребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткоеребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.
А как следить,чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построениядерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра,например (i,j), где i и j имеют разные цвета, вершинаj и все, окрашенные в ее цвет(т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершинразного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получаютодин цвет.
Докажем, что описанныйалгоритм получает в точности максимальное решение. Для доказательства нам понадобитсяочень простое утверждение:
Если к деревудобавить ребро, то в дереве появится цикл, содержащий это ребро.
Действительно,пусть добавлено ребро (u, v) — “добавлено” означает, что ребро — новое, что раньше его в деревене было. Поскольку дерево является связанным графом, то существует цепь C (u, …, v) из нескольких ребер, соединяющаявершины u иv. Добавление ребра (u, v) замыкает цепь, превращаяее в цикл.
Теорема. Алгоритм Прима-Краскалаполучает максимальное остовное дерево.
Доказательство. Результатом работы алгоритмаявляется набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершиныразного цвета, т.е. ранее не связанные. Этот граф связный, потому что после проведения1-го ребра осталось n-1 разных цветов, …, после проведения (n-1) — го ребра остался одинцвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связныйграф без циклов, содержащий n-1 ребер и n вершин. Следовательно, граф есть остовное дерево. Осталось доказать,что оно имеет минимальную длину. Пусть {/>, />, …, />} ребра остовного дерева в том порядкекак их выбирал алгоритм, т.е. />≥/>. Предположим для простоты доказательства,что все ребра сети имеют разную длину, т.е.
/>>/>>…>/>(1)
Если полученноедерево не максимально, то существует другое дерево, заданное набором из n-1 ребер {/>, />, …, />}, такое что сумма длин /> больше суммы длин/>. С точностьюдо обозначений
/>>/>>…>/>(2)
Может быть />=/>, />=/>и т.д., но так как деревьяразные, то в последовательностях (1) и (2) найдется место, где ребра отличаются.Пусть самое левое такое место — k, так, что />¹/>. Поскольку /> выбиралось по алгоритмусамым большим из не образующих цикла с ребрами />, />, …, />, то />>/>. Теперь добавим к дереву (2) ребро/>. В нем появитсяцикл, содержащий ребро /> и, может быть, какие-то (или все)ребра />, />, …, />, но они сами необразуют цикла, поэтому в цикле будет обязательно ребро d из набора />, …, />, причем d>/>. Выбросим из полученногографа с одним циклом ребро d. Мы снова получим дерево, но оно будет на d-/>короче минимального, что невозможно.Полученное противоречие доказывает теорему для сети со всеми разными ребрами.
4. Пример работы алгоритма Краскала
/>
Рисунок 1. Начальный граф
/>
Рисунок 2. Максимальное остовное дерево.
В алгоритме Краскала мы не храним массив used [N]. Вместо этогомы будем на каждой итерации алгоритма проверять, принадлежат ли концы рассматриваемогоребра к разным компонентам связности (и добавлять ребро к каркасу, если это так).
Введем счетчик int counter = 0. Пусть N — количество вершин графа.
Упорядочим список ребер по возрастанию веса.
Если counter == N — 1, закончим выполнение алгоритма.
Проходя по списку ребер, найдем ребро (i, j) такое, что i и jпринадлежат разным компонентам связности. Так как список упорядочен по возрастаниювеса ребер, мы будем выбирать ребро с максимальным весом, удовлетворяющее условию.
Добавим это ребро в каркас, увеличим на единицу счетчик counter.
Перейдем к шагу 2.
При реализации алгоритма можно использовать систему непересекающихсямножеств для проверки того, входят ли две вершины в одну компоненту связности (изначальнокаждая вершина входит в своё множество, при добавлении ребра в каркас два соответствующихмножества объединяются). Также для проверки связности двух вершин можно использоватьлюбой известный алгоритм: поиск в ширину, поиск в глубину или что-либо другое.
5. Код программы
// ---------------------------------------------
#include
#include
#include
// -------------------------------------------
typedef int* tint;// указатель на int
void main ()
{ // int max=100; // Максимальныйвес ребра
int n; // количество вершин
tint* G; // исходный граф
tint* H; // матрица списка реберс весом
tint* K; /*матрица, отмечающая принадлежность
вершины компоненте*/
tint* T; // матрица остовного дерева
tint* L; // список ребер с ценамиминимального дерева
// -----вводграфа
int max;
cout
cin>> max;
cout
cin>> n;
G=new tint [n];
for (int i=0; i
G [i] =new int[n];
cout
for (int i=1; i
for (int j=0; j
cin>> G [i][j];
}
for (int i=1; i
for (int j=0; j
G [j] [i] =G [i] [j];
// ---выделение памяти для спискаребер---
int kolreb=0;
for (int i=1; i
for (int j=0; j
if (G [i] [j]
kolreb++;
H=new tint [kolreb];
for (int i=0; i
H [i] =new int[3];
// -------------------------------------------
int a=0;
for (int i=1; i
for (int j=0; j
if (G [i] [j]
H [a] [0] =i+1;
H [a] [1] =j+1;
H [a] [2] =G [i][j];
a++;
}
cout
// ----сортировка ребер по возрастаниювеса
int f,d,s;
for (int i=0; i
for (int j=0; j
if (H [j] [2]
f=H [j] [2];
H [j] [2] =H [j+1][2];
H [j+1] [2] =f;
d=H [j] [0];
H [j] [0] =H [j+1][0];
H [j+1] [0] =d;
s=H [j] [1];
H [j] [1] =H [j+1][1];
H [j+1] [1] =s;
}
// вывод ребер отсортированных повозрастанию веса
cout
for (int i=0; i
cout";
cout
cout
cout
}
for (int i=0; i
H [i] [0] — -;
H [i] [1] — -;
}
// матрица для определения компоненты
K=new tint [n];
for (int i=0; i
K [i] =new int[2];
for (int i=0; i
K [i] [0] =i;
K [i] [1] =0;
}
// ----матрица остовного дерева
T=new tint [n];
for (int i=0; i
T [i] =new int[n];
for (int i=0; i
for (int j=0; j
T [i] [j] =0;
// -присоединение первого ребра
T [H [0] [0]] [H[0] [1]] =H [0] [2];
T [H [0] [1]] [H[0] [0]] =H [0] [2];
K [H [0] [0]] [1]=1;
K [H [0] [1]] [1] =1;
// алгорит соединения ребер без созданияцикла:
int m=2; // номер компоненты
for (int i=1; i
if (K [H [i] [0]] [1]! =K [H [i][1]] [1])
// если 2 вершины не из одной компоненты
{
if (K [H [i] [0]] [1] >0 &&K [H [i] [1]] [1] >0)
// если обе вершины принадлежат разнойкомпоненте
{
for (int j=0; j
if (K [H [i] [1]][1] ==K [j] [1])
K [j] [1] =K [H[i] [0]] [1];
K [H [i] [1]] [1]=K [H [i] [0]] [1];
T [H [i] [0]] [H[i] [1]] =H [i] [2];
T [H [i] [1]] [H[i] [0]] =H [i] [2];
}
if ( (K [H [i][0]] [1] >0 && K [H [i] [1]] [1] ==0)
|| (K [H [i] [0]] [1] ==0 &&K [H [i] [1]] [1] >0))
// если одна вершина имеет компонентуа др. нет
{
if (K [H [i] [0]][1]! =0)
K [H [i] [1]] [1]=K [H [i] [0]] [1];
if (K [H [i] [1]][1]! =0)
K [H [i] [0]] [1]=K [H [i] [1]] [1];
T [H [i] [0]] [H[i] [1]] =H [i] [2];
T [H [i] [1]] [H[i] [0]] =H [i] [2];
}
if (K [H [i] [0]] [1] ==0 &&K [H [i] [1]] [1] ==0)
// если обе вершины не имели компоненты
{
K [H [i] [0]] [1]=m;
K [H [i] [1]] [1]=m;
T [H [i] [0]] [H[i] [1]] =H [i] [2];
T [H [i] [1]] [H [i] [0]] =H [i][2];
m++;
}
} // конец проверки всех ребер
// ---выделение памяти для спискаребер
kolreb=0;
for (int i=1; i
for (int j=0; j
if (T [i] [j]
kolreb++;
L=new tint [kolreb];
for (int i=0; i
L [i] =new int[3];
// ------------------------------------------
// ---выводребер
cout
a=0;
for (int i=1; i
for (int j=0; j
if (T [i] [j]
L [a] [0] =i+1;
L [a] [1] =j+1;
L [a] [2] =T [i][j];
a++;
}
for (int i=0; i
cout";
cout
cout
}
int b=0;
for (int i=0; i
b+=L [i] [2];
cout
getch ();
// return 0;
}
// --------------------------------------------------------------
6. Обзор работы программы
/>
После выполнения программы выводятся ребра максимального веса,и стоимость остовного дерева.
Заключение
В курсовом проекте был разработана программа, реализующая алгоритмКраскала, поиск максимального остовного дерева.
Алгоритм Краскаладействительно находит остовный лес максимального веса, поскольку он является частнымслучаем алгоритма Радо — Эдмондса для графического матроида, где независимые множества- ациклические множества рёбер.
Список использованной литературы
1. Рыбаков Глеб. Минимальные остовные деревья.
2. Архангельский А.Я., C++Builder 6. Справочное пособие.
3. Белов Теория Графов, Москва, «Наука», 1968.
4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.- М.: Энергоатомиздат, 1988.
5. http://rain. ifmo.ru