Смекни!
smekni.com

Нахождение минимального остовного дерева алгоритмом Краскала (стр. 2 из 2)

>
>…>
(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 <stdio. h>

#include <conio. h>

#include <iostream. h>

// -------------------------------------------

typedef int* tint; // указатель на int

void main ()

{ // int max=100; // Максимальный вес ребра

int n; // количество вершин

tint* G; // исходный граф

tint* H; // матрица списка ребер с весом

tint* K; /*матрица, отмечающая принадлежность

вершины компоненте*/

tint* T; // матрица остовного дерева

tint* L; // список ребер с ценами минимального дерева

// -----ввод графа

int max;

cout<<" Maximalno dopustimoe zna4enie vesa rebra = ";

cin>> max;

cout<<"&bsol;n Vvedite 4ilo vershin: &bsol;n ";

cin>> n;

G=new tint [n];

for (int i=0; i<n; i++)

G [i] =new int [n];

cout<<" Vvedite nignij treugolnik matrici stoimosti: &bsol;n ";

for (int i=1; i<n; i++)

for (int j=0; j<i; j++) {

cin>> G [i] [j];

}

for (int i=1; i<n; i++)

for (int j=0; j<i; j++)

G [j] [i] =G [i] [j];

// ---выделение памяти для списка ребер---

int kolreb=0;

for (int i=1; i<n; i++)

for (int j=0; j<i; j++)

if (G [i] [j] <max && G [i] [j]! =0)

kolreb++;

H=new tint [kolreb];

for (int i=0; i<kolreb; i++)

H [i] =new int [3];

// -------------------------------------------

int a=0;

for (int i=1; i<n; i++)

for (int j=0; j<i; j++)

if (G [i] [j] <max && G [i] [j]! =0) {

H [a] [0] =i+1;

H [a] [1] =j+1;

H [a] [2] =G [i] [j];

a++;

}

cout<<endl;

// ----сортировка ребер по возрастанию веса

int f,d,s;

for (int i=0; i<kolreb-1; i++)

for (int j=0; j<kolreb-1; j++)

if (H [j] [2] <H [j+1] [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<<"Matrica dostigimosni otsortirovannoe po ubivaniuy: &bsol;n ";

for (int i=0; i<kolreb; i++) {

cout<<H [i] [0] <<"-->";

cout<<H [i] [1] <<" = ";

cout<<H [i] [2] <<endl;

cout<<" ";

}

for (int i=0; i<kolreb; i++) {

H [i] [0] - -;

H [i] [1] - -;

}

// матрица для определения компоненты

K=new tint [n];

for (int i=0; i<n; i++)

K [i] =new int [2];

for (int i=0; i<n; i++) {

K [i] [0] =i;

K [i] [1] =0;

}

// ----матрица остовного дерева

T=new tint [n];

for (int i=0; i<n; i++)

T [i] =new int [n];

for (int i=0; i<n; i++)

for (int j=0; j<n; 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<kolreb; 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<n; 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<n; i++)

for (int j=0; j<i; j++)

if (T [i] [j] <max && T [i] [j]! =0)

kolreb++;

L=new tint [kolreb];

for (int i=0; i<kolreb; i++)

L [i] =new int [3];

// ------------------------------------------

// ---вывод ребер

cout<<endl<<" Vivod reber maximalnogo vesa: &bsol;n ";

a=0;

for (int i=1; i<n; i++)

for (int j=0; j<i; j++)

if (T [i] [j] <max && T [i] [j]! =0) {

L [a] [0] =i+1;

L [a] [1] =j+1;

L [a] [2] =T [i] [j];

a++;

}

for (int i=0; i<kolreb; i++) {

cout<<L [i] [0] <<"-->";

cout<<L [i] [1] <<" = ";

cout<<L [i] [2] <<"&bsol;n ";

}

int b=0;

for (int i=0; i<kolreb; i++)

b+=L [i] [2];

cout<<endl <<" Stoimost dereva = "<<b; // вывод стоимости

getch ();

// return 0;

}

// --------------------------------------------------------------

6. Обзор работы программы

После выполнения программы выводятся ребра максимального веса, и стоимость остовного дерева.

Заключение

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

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

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

1. Рыбаков Глеб. Минимальные остовные деревья.

2. Архангельский А.Я., C++Builder6. Справочное пособие.

3. Белов Теория Графов, Москва, "Наука", 1968.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988.

5. http://rain. ifmo.ru