Нахождение остовного леса минимального веса с помощью Метода Прима для графа

Министерство образования Российской Федерации

Государственное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет»

Факультет компьютерных технологий

Кафедра МОП ЭВМ

Лабораторная работа 

по курсу: «Структуры и алгоритмы обработки данных»

Выполнила студентка группы 1ВТ1:                                            Кондырева Т.В.

Преподаватель:                                                                                Изабеков З.А..

2004

Задание:

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

Ход работы:

Алгоритм Прима. Задан граф (V, E) и функция w: E ® R, принимающая неотрицательные значения. Требуется построить максимальное дерево T, содержащее заданную вершину vÎV и содержащееся в графе (V, E), такое что сумма  минимальна.

Шаг 1.      Полагаем U = {v}, T = Æ. Элементы из U удобно представлять себе как раскрашенные вершины, а из V\U – как нераскрашенные.

Шаг 2.      Пока есть рёбра {u, }, у которых одна вершина раскрашена, другая нераскрашена, u Î U,  Î V\U, выбираем из них ребро минимального веса, устанавливаем

и раскрашиваем вершину  с помощью операции

.

(Конец цикла.)

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

Текст программы:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

FILE *out;

// Класс списка ребер

class elist

{private:

int from, to; // Первая и вторая вершины ребра

int lenght; // Длина(вес) ребра

elist *next; // Указатель на следующий элемент списка

// Метод рекурсивного добавления в конец списка

elist *add(int f, int t, int v=1)

{   // Если конец списка - вставить ребро

if (this==NULL) return new elist(f, t, v);

// Если уже существует - ничего не делать

if (inedge(f) && contr(f)==t) return this;

next=next->add(f, t, v); // Рекурсивный вызов

return this;

}

public:

// Конструкторы

elist(int f, int t, int l=1) { init(f, t, l); next=NULL; }

elist() { init(-1, -1); next=NULL; }

// Метод инициализации

void init(int f, int t, int l=1) { from=f; to=t; lenght=l; }

void init(elist *e) { init(e->from, e->to, e->lenght); }

// Метод проверки наличия вершины в ребре

// Возвращает 1 если есть, 0 если нет

int inedge(int v) { return (v==from || v==to)?1:0; }

// Метод возвращает вершину противоположную v

int contr(int v)

{   if (v==from) return to;

else if (v==to) return from;

else return -1; // Если v нет в ребре

}

// Метод возвращает длину ребра

int len() { return lenght; }

// Описание интерфейсных функций

friend void add(elist **, int, int, int);

friend void add(elist **e, elist *ee)

{ ::add(e, ee->from, ee->to, ee->lenght); }

friend void erase(elist **);

friend void display(elist *);

friend int clean();

friend void work(int);

} *base;

// Функция очистки списка

void erase(elist **e)

{   if (e==NULL || *e==NULL) return;

elist *ee=(*e)->next; // Начиная со второго

while(ee!=NULL)

{   elist *t=ee;

ee=ee->next;

delete t; // Удаление первого

}

delete *e;

*e=NULL;

}

// Функция отображения списка

void display(elist *e)

{   elist *ee=e; // Счетчик ребер

int c=0, l=0; // Суммарная длина всех ребер списка

while (ee!=NULL)

{ fprintf(out, "%d,%d=%d\n", ee->from, ee->to, ee->lenght);

c++; l+=ee->lenght;

ee=ee->next;

}

fprintf(out, "-------------------\n%d items\nOverall price =%d\n", c, l);

}

// Функция добавления ребра (f, t, v) в список e

void add(elist **e, int f, int t, int v=1)

{   if (e==NULL) return;

*e=(*e)->add(f, t, v);

}

int *c; // Массив меток всех вершин

int max; // Число элементов в нем

// Функция очистки c[]

int clean()

{   int i;

for (i=0; i<max; i++) // Заполнение -1

c[i]=-1;

elist *e=base;

while (e)

{ c[e->from]=0; c[e->to]=0; // Пометить вершины ребра 0

e=e->next;

}

// Неиспользуемые вершины будут помечены -1

int n=0;

for (i=0; i<max; i++)

if (c[i]==0) n++;

return n; // Число используемых вершин в графе

}

// Функция чтения из файла графа

int input(char *filename)

{  FILE *file=fopen(filename, "r");

if (file==NULL)

{ printf("Error opening file.\n");

return 0;

}

max=-1; // Номер максимальной вершины

while(feof(file)==0)

{ int f, t, v;

if (fscanf(file, "%d,%d=%d", &f, &t, &v)!=3)

{   printf("File format error.\n");

fclose(file);

return 0;

}

add(&base, f, t, v); // Добавление ребра в список

// Поиск максимального номера

if (f>max) max=f;

if (t>max) max=t;

}

fclose(file);

c=new int[max]; // Выделение памяти под метки вершин

if (c==NULL)

{ printf("Too many verts.\n");

return 0;

}

fprintf(out, "There are %d cities.\n=====================\n",

clean());

return 1;

}

// Функция, которая и выполняет всю работу

void work(int k) // k - номер вершины, с которой нужно начинать

{   elist *result=NULL; // Результирующий список

clean(); // Очистить метки

c[k]=1; // Пометить начальную вершину

while (1)

{ elist min; // Минимальное ребро

min.init(-1, -1, 1000);

for (int i=0; i<max; i++) // Цикл по всем вершинам

if (c[i]==1) // Если первая вершина помечена

{ // Перебор списка ребер на наличие смежных с i-ой

elist *e=base;

while (e)

{    // Если есть ребро, у которого на одномконце i-ая вершина,

// а на другом непомеченная и длина этого ребра меньше

// длины минимального, то

if (e->inedge(i) && c[e->contr(i)]==0 && min.lenght>e->lenght )

min.init(i, e->contr(i), e->lenght); // Новый минимум

e=e->next;

}

}

if (min.lenght==1000) break; // Если не найдено

add(&result, &min); // Добавить это ребро в результат

c[min.to]=1; // Пометить вторую вершину ребра

}

display(result);

erase(&result);

}

int main()

{  if (!input("myin.txt")) return 1;

if ((out=fopen("myout.txt", "w"))==NULL)

{ printf("Error opening file.");

return 1;

}

fprintf(out, "Base tree:\n");

display(base);

randomize();

int k=random(max); // Выбирается любая вершина, и от нее строится остов

fprintf(out, "\nSkeleton tree from %d city:\n", k);

work(k);

erase(&base);

delete[] c;

return 0;

}

Результат выполнения программы.

Содержимое файла myout.txt:

Base tree:

0,2=6

0,5=3

0,12=7

1,2=2

2,5=5

2,7=4

3,7=7

4,6=3

4,7=5

5,13=8

5,14=1

6,9=2

6,10=1

6,11=9

8,9=5

10,15=3

10,16=6

11,14=8

11,15=2

13,14=3

------------------20 items

Overall price =90

Skeleton tree from 11 city:

11,15=2

15,10=3

10,6=1

6,9=2

6,4=3

4,7=5

7,2=4

2,1=2

2,5=5

5,14=1

5,0=3

14,13=3

9,8=5

10,16=6

0,12=7

7,3=7

------------------16 items

Overall price =59