Расчетно-графическая работа по предмету «Структуры и алгоритмы обработки данных»

Министерство образования РФ

НГТУ

Факультет АВТ

Расчетно-графическая работа

по предмету

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

Варианты задания: 13, 14, 14

Выполнил: Проверил:

Студентка группы АМ – 110 преподаватель

Скопина Т. А.

Новосибирск
2004 г.

Задание

Часть 1.

Разработать АТД «Случайный неориентированный граф». Форма представления графа G(V, E) определяется коэффициентом насыщенности R=2E/V. Граф не содержит петель и параллельных ребер.

Интерфейс АТД «Случайный неориентированный граф» включает операции:

V() - опрос числа вершин в графе,

E() - опрос числа ребер в графе,

Directed() - опрос типа графа (ориентированный / неориентированный),

Insert(v1,v2) - вставка ребра, соединяющего вершины v1, v2,

Delete(v1,v2) - удаление ребра, соединяющего вершины v1, v2,

Edge(v1,v2) - опрос наличия ребра, соединяющего вершины v1, v2,

Iterator(v) - создание итератора смежных вершин для вершины v,

Iterator.beg() - опрос первой смежной вершины для вершины v,

Iterator.end() - опрос конца списка смежных вершин для вершины v,

Iterator.next()- опрос следующей смежной вершины для вершины v,

Show() - вывод изображения на экран,

DFS() - обход вершин при поиске в глубину от заданной вершины v,

BFS() - обход вершин при поиске в ширину от заданной вершины v,

На основе АТД «Случайный неориентированный граф» реализовать и провести эмпирические исследования времени и вычислительной сложности алгоритма: (вариант 13) определение диаметра графа методом поиска в ширину (предусмотреть случай несвязного графа).

Часть 2.

Разработать АТД «Случайный ориентированный граф». Форма представления графа G(V, E) определяется коэффициентом насыщенности R=2E/V. Граф не содержит петель и параллельных ребер.

Интерфейс АТД «Случайный ориентированный граф» включает операции:

V() - опрос числа вершин в графе,

E() - опрос числа ребер в графе,

Directed() - опрос типа графа (ориентированный / неориентированный),

Insert(v1,v2) - вставка ребра, соединяющего вершины v1, v2,

Delete(v1,v2) - удаление ребра, соединяющего вершины v1, v2,

Edge(v1,v2) - опрос наличия ребра, соединяющего вершины v1, v2,

Iterator(v) - создание итератора смежных вершин для вершины v,

Iterator.beg() - опрос первой смежной вершины для вершины v,

Iterator.end() - опрос конца списка смежных вершин для вершины v,

Iterator.next()- опрос следующей смежной вершины для вершины v,

Show() - вывод изображения на экран,

DFS() - обход вершин при поиске в глубину от заданной вершины v,

BFS() - обход вершин при поиске в ширину от заданной вершины v,

На основе АТД «Случайный ориентированный граф» реализовать и провести эмпирические исследования времени и вычислительной сложности алгоритма:(14 вариант) Построение остовного дерева от заданной вершины орграфа методом поиска в глубину.

Часть 3.

Разработать АТД «Случайный взвешенный ориентированный граф». Форма представления графа G(V, E) определяется коэффициентом насыщенности R=2E/V. Граф не содержит петель и параллельных ребер.

Интерфейс АТД «Случайный ориентированный граф» включает операции:

V() - опрос числа вершин в графе,

E() - опрос числа ребер в графе,

Directed() - опрос типа графа (ориентированный / неориентированный),

Insert(v1,v2) - вставка ребра, соединяющего вершины v1, v2,

Delete(v1,v2) - удаление ребра, соединяющего вершины v1, v2,

Edge(v1,v2) - опрос наличия ребра, соединяющего вершины v1, v2,

Iterator(v) - создание итератора смежных вершин для вершины v,

Iterator.beg() - опрос первой смежной вершины для вершины v,

Iterator.end() - опрос конца списка смежных вершин для вершины v,

Iterator.next()- опрос следующей смежной вершины для вершины v,

Show() - вывод изображения на экран,

DFS() - обход вершин при поиске в глубину от заданной вершины v,

BFS() - обход вершин при поиске в ширину от заданной вершины v,

На основе АТД «Случайный взвешенный ориентированный граф» реализовать и провести эмпирические исследования времени и вычислительной сложности алгоритма (вариант 14) определения кратчайших путей из заданной вершины взвешенного орграфа с отрицательными весами ребер на основе алгоритма Беллмана – Форда.

1. Формат АТД

Спецификация АТД для класса граф:

Данные:

Количество вершин (_e)

Количество рёбер (_v)

Максимальное количество рёбер (maxE)

Операции:

Конструктор:

Вход: количество вершин (e), количество рёбер (v)

Предусловие: 1) e>0, v>=0;

2) v<maxE;

Процесс: создание пустого графа.

V:

Вход: нет;

Предусловие: нет;

Процесс: чтение значения числа вершин графа (_v);

Выход: значение числа вершин в графе;

Постусловие: нет.

E:

Вход: нет;

Предусловие: нет;

Процесс: чтение значения числа ребер графа (_e);

Выход: значение числа рёбер в графе

Постусловие: нет

Insert:

Вход: вершина начальная (v1), вершина конечная (v2), (вес ребра);

Предусловие: 1) v1,v2 принадлежат графу;

2) v1!=v2;

3) ребра нет в графе;

Процесс: вставка ребра в граф соединяющего заданные вершины;

Выход: если выполнены предусловия – 0;

если не выполнено предусловие 1) -1; 2) -2; 3) 1.

Постусловие: счётчик рёбер увеличен на 1, граф с новым ребром.

Delete:

Вход: вершина начальная (v1), вершина конечная (v2);

Предусловие: 1) v1,v2 принадлежат графу;

2) v1!=v2;

3) ребро есть в графе;

Процесс: удаление ребра из графа

Выход: если выполнены предусловия – 0;

если не выполнено предусловие 1) -1; 2) -2; 3) 1.

Постусловие: счётчик рёбер уменьшен на 1, граф без ребра.

Edge:

Вход: вершина начальная (v1), вершина конечная (v2);

Предусловие: ребро есть в графе.

Процесс: опрос наличия ребра

Выход: если выполнено предусловие – true; если не выполнено false.

Постусловие: нет.

Iterator:

Вход: начальная вершина;

Предусловие: нет;

Процесс: инициализация итератора;

Выход: нет;

Постусловие: нет;

IteratorBeg:

Вход: нет;

Предусловие: существует смежная вершина;

Процесс: опрос первой смежной вершины;

Выход: если выполнено предусловие – номер первой смежной вершины;

если не выполнено -1;

Постусловие: нет;

IteratorNext:

Вход: нет;

Предусловие: существует следующая смежная вершина;

Процесс: опрос следующей смежной вершины;

Выход: если выполнено предусловие – номер первой смежной вершины;

если не выполнено -1;

Постусловие: нет;

IteratorEnd:

Вход: нет;

Предусловие: существует смежная вершина;

Процесс: опрос последней смежной вершины;

Выход: если выполнено предусловие – номер последней смежной вершины;

если не выполнено -1;

Постусловие: нет;

DFS:

Вход: начальная вершина (v);

Предусловие: v принадлежит графу;

Процесс: обход графа в глубину, начиная с вершины v;

Выход: если не выполнено предусловие - false; если выполнено true;

Постусловие: заполнены массивы цветов(cc), меток времени (dd, tt), родителей (pp);

BFS:

Вход: начальная вершина (v);

Предусловие: v принадлежит графу;

Процесс: обход графа в ширину, начиная с вершины v;

Выход: если выполнено предусловие – true; если не выполнено false;

Постусловие: заполнены массивы цветов(cc), меток обхода (dd), родителей (pp);

GetNumEdge:

Вход: начальная вершина (v);

Предусловие: v принадлежит графу;

Процесс: подсчёт количества смежных вершин.

Выход: если выполнено предусловие – количество смежных вершин; если не выполнено исключение типа unsigned;

Постусловие: нет;

Directed:

Вход: нет;

Предусловие: нет;

Процесс: опрос типа графа;

Выход: тип графа (0-неорграф, 1-орграф, 2-взвешенный орграф);

Постусловие: нет

Структурное описание:

2. Описание классов.

Алгоритм определение диаметра графа методом поиска в ширину (предусмотреть случай несвязного графа).

Алгоритм определения диаметра графа методом поиска в ширину с учетом возможной несвязности графа базируется на поиске в ширину. Поскольку поиск в ширину, будучи вызванным для какой-то конкретной вершины, дает все расстояния от этой вершины до всех остальных (в пределах одной связной компоненты), то решение задачи сводится к последовательному вызову алгоритма BFS для каждой вершины и последующим поиском пары вершин с максимальным расстоянием друг от друга. Это расстояние и является диаметром не ориентированного графа, выраженное в количестве ребер. Случай несвязного графа предусматривается, как уже было упомянуто, в результате вызова алгоритма BFS для каждой вершины в отдельности. Трудоемкость алгоритма - O(V(V + E)), т. к. количество вызовов процедуры поиска в ширину равняется количеству вершин в графе.

Алгоритм Построения остовного дерева от заданной вершины орграфа методом поиска в глубину.
Этот алгоритм базируется на основе алгоритма обхода дерева в глубину (DFS, DFS_Visit), где из DFS вызывается функция DFS_Visit для некоторой не просмотренной вершины, которая является корнем остовного дерева. По окончании функции DFS будет заполнен массив, содержащий для каждой вершины номер вершины-предка; т. е. вершины, у которых он не определён, и являются корнями остовных деревьев. Даже в самом худшем случае максимальное время выполнения будет иметь порядок O(V+E).

Алгоритм определения кратчайших путей из заданной вершины взвешенного орграфа с отрицательными весами ребер на основе алгоритма Беллмана – Форда.

Алгоритм просматривает все вершины графа и производит релаксацию всех ребер. Время работы этой части оценивается как O(V+E). Эту операцию алгоритм повторяет для каждой вершины для того, чтобы сформировать путь с кратчайшим весом. Поэтому время работы алгоритма оценивается как O(V2 +V*E). Затем алгоритм проверяет, нет ли цикла отрицательного веса, достижимого из каждой вершины. Затраты на выполнение этой операции, в случае отсутствия отрицательных циклов оценивается как O(V). Но практически, данные затраты времени не превышает нескольких единиц, так как большинство циклов выявляется на первых шагах выполнения данной части алгоритма.

Общее время работы алгоритма определения кратчайших путей из заданной вершины взвешенного орграфа оценивается как O(V2 +V*E).

Описание классов:

class matrix

{protected:

int *p; // Указатель на массив элементов

struct edge_iterator //Структура итератора для каждой вершины

{edge_iterator*next; //Указатель на сл. элемент

unsigned v; //Для какой вершины

int offset; //Смещение

}

*f; // Указатель на список итераторов

edge_iterator*curr; // Указатель на текущий итератор

const unsigned size; // размер матрицы

public:

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

matrix(unsigned s):size(s),f(NULL)

//Деструктор

~matrix()

//Подсчёт смежных вершин

long GetNumEdge(unsigned v)

//получить данные из ячейки x, y

int get(unsigned x, unsigned y)

//Сохранить данные в ячейке x, y

void put(unsigned x, unsigned y, int d)

//Настройка итератора

void iterator(unsigned v)

//Настройка на первую смежную вершину

unsigned beg()

//Позиционирование на последнюю смежную вершину

unsigned end() };

class list

{protected:

struct elemList{

elemList*next; //Указатель на след. элемент

unsigned n; //Номер элемента

int w; //Вес ребра

}

**p; //Указатель на массив списков

struct edge_iterator //Структура итератора для каждой вершины

{edge_iterator*next; //Указатель на сл. элемент

unsigned v; //Для какой вершины

elemList*offset; //Смещение

}

*f; //Указатель на начало

edge_iterator*curr; //Указатель на текущий итератор

const unsigned size; //размер матрицы

public:

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

list(unsigned s):size(s),f(NULL)

//Деструктор

~list()

//Подсчёт смежных вершин

long GetNumEdge(unsigned v)

//получить данные из ячейки x, y

int get(unsigned x, unsigned y)

//Сохранить данные в ячейке x, y

void put(unsigned x, unsigned y, int d)

//Настройка итератора

void iterator(unsigned v)

//Настройка на первую смежную вершину

unsigned beg()

//Следующая смежная вершина

unsigned next()

//Позиционирование на последнюю смежную вершину

unsigned end()

};

template <class T>

class CFIFO //First In - First Out

{int Num; //Количество элементов

T*Data; //Указатель на данные

int Count; //Количество элементов очереди

int GetNext; //Индекс сл. элемента

int PutNext; //Индекс сл. для вставки элемента

public:

CFIFO (int num=100)

~CFIFO()

void Add(T dd)

void Get(T&dd)

bool Peek(T&dd)

inline int GetCount()

};

struct VD{long v;long d;}; //Структура для внутренних целей

class CFIFO_Prior

{VD *mass; //Массив с данными

int sz; //Размер массива

int count; //Количество элементов

public:

CFIFO_Prior(int num):sz(num),count(0)

bool Add(int v, int d)

void Shift()

bool Get(int&v, int&d)

bool Set(const int v, const int d)

bool Search(const int v)

inline int GetCount()

};

class NeOrGraph

{protected:

long _v; //Счётчик вершин

long _e; //Счётчик рёбер

matrix * p_m; //Указатель на матрицу смежности

list * p_l; //Указатель на список смежности

unsigned long maxE; //Максимальное количество рёбер

public:

NeOrGraph(int V, int E):_e(0),_v(V),p_m(NULL),p_l(NULL),maxE(0)

virtual ~NeOrGraph()

inline long V() //количество вершин

inline long E() //количество рёбер

//тип графа

virtual inline long Directed()

//вставка ребра, соединяющего v1 и v2

virtual long Insert(int v1, int v2)

//удаление ребра, соединяющего v1 и v2

long Delete(int v1, int v2)

//опрос наличия ребра соединяющего v1 и v2

bool Edge(int v1, int v2)

//Получить вес ребра

long getW(int v1,int v2)

//Итератор

void Iterator(int v)

//Первая вершина

long IteratorBeg()

//Следующая вершина

long IteratorNext()

//конечная вершина

long IteratorEnd()

private:

void DFS_Visit(int v)

public:

bool DFS(int v)

bool BFS(int v) //Инициализация структур возложена на управляющую программу

//количество смежных вершин

long GetNumEdge(int v)

void Show(CDC*dc, RECT r)

protected:

void arrow(int x1,int y1,int x2,int y2,CDC*dc) // Прорисовка стрелочки для орграфов

virtual void printV(int v, CDC*dc, int x, int y)

protected:

virtual void printE(int v1, int v2, CDC*dc, CPoint center)

public:

bool Dijekstor(int v, CFIFO_Prior&cfp)

//Тестирование без отображения

private:

void work_func1(int v) // Аналог DFS_Visit

public:

void Task1()

//Тестирование без отображения

private:

void work_func2(int v) //Аналог DFS_Visit

public:

void Task2()

//Тестирование без отображения

void Task3(int v)

};

class OrGraph:public NeOrGraph

{public:

OrGraph(int V, int E):NeOrGraph(V, E/2)

~OrGraph()

//тип графа

virtual inline long Directed()

};

class VOrGraph:public OrGraph

{public:

//тип графа

virtual inline long Directed()

VOrGraph(int V, int E):OrGraph(V, E)

~VOrGraph()

{}

//вставка ребра, соединяющего v1 и v2 с весом w

virtual long Insert(int v1, int v2, int w)

};

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

4.1. Алгоритм определение диаметра графа методом поиска в ширину

Алгоритм Построения остовного дерева от заданной вершины орграфа методом поиска в глубину.

Алгоритм определения кратчайших путей из заданной вершины взвешенного орграфа с отрицательными весами ребер на основе алгоритма Беллмана – Форда.(для V=1000)

Начальная инициализация массивов возложена на вызывающие функции.

Вывод:

В результате проделанной работы была разработана структура АТД граф и проведены исследования трех алгоритмов по заданию. Практически полученные трудоемкости всех протестированных алгоритмов соответствуют теоретическим оценкам.

Список литературы

1.  Лекции по курсу «Структуры и алгоритмы обработки данных».

2.  «Фундаментальные алгортимы на С++. Том 5.» // Киев, 2001г.

3.  «Структуры данных и алгоритмы».// Москва, 2000 г.

Приложение

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

Class.h

#include <fstream. h>

#include <conio. h>

#include <math. h>

#include <windows. h>

class matrix;

class list;

class OrGraph;

template<typename T>

class CFIFO;

CPoint deg2coord(CPoint, unsigned int, short);

static int result=0; // Глобальная переменная, чтобы меньше памяти использовать

static RECT r_paint={10,0,490,400}; // Область рисования

static COLORREF attr=RGB(200,230,200); // Атрибуты элементов по умолчанию

static COLORREF * cc=NULL; // Массив цветов для вершин

static unsigned int * dd=NULL; // Массив длин путей для BFS и DFS

static int * tt=NULL; // Массив обратных меток для DFS

static int ttime=0; // Метка времени, используется в DFS

static int * pp=NULL; // Указатель на массив предков

static list * ww=NULL; // Массив для ширины рёбер

static CFIFO<int>* cf=NULL; // Указатель для топологической сортировки

static int ViewEdge=0; // Количество просмотренных рёбер при тестировании

class matrix

{protected:

int *p; //Указатель на массив элементов

struct edge_iterator //Структура итератора для каждой вершины

{edge_iterator*next; //Указатель на сл. элемент

unsigned v; //Для какой вершины

int offset; // Смещение

}

*f; // Указатель на список итераторов

edge_iterator*curr; // Указатель на текущий итератор

const unsigned size; // размер матрицы

public:

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

matrix(unsigned s):size(s),f(NULL)

{p=new int[size*size];

for(unsigned i=0;i<size*size;i++)p[i]=INT_MAX; // Забить всю матрицу максимальными элементами

}

//- Деструктор

~matrix(){delete [] p;}

//- Подсчёт смежных вершин

long GetNumEdge(unsigned v)

{if(v<0 || v>=size)throw v;

int n=0;

for(unsigned i=0;i<size;i++)

if(get(v, i)!=INT_MAX)n++;

return n;

}

//- получить данные из ячейки x, y

int get(unsigned x, unsigned y)

{if(x<size && y<size)

return p[x*size+y];

throw x;

}

//- Сохранить данные в ячейке x, y

void put(unsigned x, unsigned y, int d)

{if(x<size && y<size)

{p[x*size+y]=d;return;}

throw x;

}

//- Настройка итератора

void iterator(unsigned v)

{if(f==NULL)

{f=new edge_iterator;f->next=NULL;f->offset=-1;f->v=v;curr=f;return;}

curr=f;

do{

if(curr->v==v){/*curr->offset=-1;*/return;}

if(curr->next==NULL)break;

curr=curr->next;

}while(1);

curr->next=new edge_iterator;

curr=curr->next;

curr->next=NULL;curr->offset=-1;curr->v=v;

}

//- Настройка на первую смежную вершину

unsigned beg()

{curr->offset=-1;

return next();

}

//- Следующая смежная вершина

unsigned next()

{for(curr->offset++; (unsigned)curr->offset<size; curr->offset++)

if(p[curr->v*size+curr->offset]!=INT_MAX)return curr->offset;

curr->offset=-1;

return curr->offset;

}

//- Позиционирование на последнюю смежную вершину

unsigned end()

{for(curr->offset=size-1; curr->offset>=0; curr->offset--)

if( p[ curr->v*size+curr->offset]!=INT_MAX )break;

return curr->offset;

}

};

class list

{protected:

struct elemList{

elemList*next; // Указатель на след. элемент

unsigned n; // Номер элемента

int w; // Вес ребра

}

**p; // Указатель на массив списков

struct edge_iterator // Структура итератора для каждой вершины

{edge_iterator*next; // Указатель на сл. элемент

unsigned v; // Для какой вершины

elemList*offset; // Смещение

}

*f; // Указатель на начало

edge_iterator*curr; // Указатель на текущий итератор

const unsigned size; // размер матрицы

public:

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

list(unsigned s):size(s),f(NULL)

{p=(elemList**)new elemList[size]; // Создать массив

for(unsigned i=0;i<size;i++)p[i]=NULL; // Забить всю матрицу максимальными элементами

}

//- Деструктор

~list(){delete [] p;}

//- Подсчёт смежных вершин

long GetNumEdge(unsigned v)

{if(v<0 || v>=size)throw v;

int n=0;

for(elemList*t=p[v];t!=NULL;n++,t=t->next);

return n;

}

//- получить данные из ячейки x, y

int get(unsigned x, unsigned y)

{if(this==NULL)

return 0;

if(x>=size || y>=size)

throw x;

for(elemList*tmp=p[x];tmp!=NULL;tmp=tmp->next)

if(tmp->n==y)return tmp->w;

return INT_MAX;

}

//- Сохранить данные в ячейке x, y

void put(unsigned x, unsigned y, int d)

{if(x>=size && y>=size)

throw x;

elemList*tmp;

if(p[x]!=NULL)

{ tmp=p[x];

do{

if(tmp->n==y)

{tmp->w=d;return;}

if(tmp->next==NULL)break;

tmp=tmp->next;

}while(1);

tmp->next=new elemList;

tmp=tmp->next;

}else {p[x]=new elemList;tmp=p[x];}

tmp->next=NULL;

tmp->n=y;

tmp->w=d;

}

//- Настройка итератора

void iterator(unsigned v)

{if(f==NULL)

{f=new edge_iterator;f->next=NULL;f->offset=NULL;f->v=v;curr=f;return;}

curr=f;

do{

if(curr->v==v){/*curr->offset=NULL;*/return;}

if(curr->next==NULL)break;

curr=curr->next;

}while(1);

curr->next=new edge_iterator;

curr=curr->next;

curr->next=NULL;curr->offset=NULL;curr->v=v;

}

//- Настройка на первую смежную вершину unsigned beg()

{curr->offset=NULL;

return next();

}

//- Следующая смежная вершина unsigned next()

{if(curr->offset==NULL)

{curr->offset=p[curr->v];}

else {curr->offset=curr->offset->next;}

for(;curr->offset!=NULL; curr->offset=curr->offset->next)

if(curr->offset->w!=INT_MAX)return curr->offset->n;

return -1;

}

//- Позиционирование на последнюю смежную вершину unsigned end()

{elemList*tmp=NULL;

curr->offset=p[curr->v];

if(curr->offset==NULL)return -1;

do{if(curr->offset->w!=INT_MAX) tmp=curr->offset;

curr->offset=curr->offset->next;

}while(curr->offset!=NULL);

if(tmp==NULL)return -1;

return tmp->n;

}

};

template <class T>

class CFIFO // First In - First Out

{int Num; // Количество элементов

T*Data; // Указатель на данные

int Count; // Количество элементов очереди

int GetNext; // Индекс сл. элемента

int PutNext; // Индекс сл. для вставки элемента

public:

CFIFO (int num=100){Num=num;GetNext=0;PutNext=0;Count=0; Data=new T[Num];}

~CFIFO() {delete Data;}

void Add(T dd) {Data[PutNext++]=dd;Count++;if(PutNext==Num)PutNext=0;}

void Get(T&dd)

{if(Count==0)throw(dd);

dd=Data[GetNext++];

if(GetNext==Num)

GetNext=0;

Count--; }

bool Peek(T&dd){if(Count==0)return false;dd=Data[GetNext];return true;}

inline int GetCount(){return Count;}

};

struct VD{long v;long d;}; // Структура для внутренних целей

class CFIFO_Prior

{VD *mass; // Массив с данными

int sz; // Размер массива

int count; // Количество элементов

public:

CFIFO_Prior(int num):sz(num),count(0)

{if(num<=0)throw num;

mass=new VD[num+1];

}

~CFIFO_Prior(){delete mass;}

bool Add(int v, int d)

{if(count==sz)return false;

count++;

mass[count].v=v;mass[count].d=d;// Включить без просеивания

for(int i=count;i!=1;i=i/2) // Просеивание нового элемента

{if( mass[i].d<mass[i/2].d )

{d=mass[i].d; mass[i].d=mass[i/2].d; mass[i/2].d=d; // 3 стакана

v=mass[i].v; mass[i].v=mass[i/2].v; mass[i/2].v=v; // 3 стакана

}

}

return true;

}

void Shift()

{int i=1;

int j=2*i;

int x=mass[i].d; int v=mass[i].v;

if(j<=count && mass[j+1].d<mass[j].d)

j++;

while( j<=count+1 && mass[j].d<x )

{mass[i].d=mass[j].d; mass[i].v=mass[j].v;

i=j; j=2*i;

if( j<=count && mass[j+1].d<mass[j].d )

{j++;}

}

mass[i].d=x; mass[i].v=v;

}

bool Get(int&v, int&d)

{if(count==0)return false;

v=mass[1].v; d=mass[1].d;

mass[1].v=mass[count].v; mass[1].d=mass[count].d;

count--;

Shift();

return true;

}

bool Set(const int v, const int d)

{for(int i=1;i<=count;i++)

if(mass[i].v==v){mass[i].d=d;Shift();return true;}

return false;

}

bool Search(const int v)

{for(int i=1;i<=count;i++)

if(mass[i].v==v){return true;}

return false;

}

inline int GetCount()

{return count;

}

};

const RADIUS=160;

class NeOrGraph

{protected:

long _v; // Счётчик вершин

long _e; // Счётчик рёбер

matrix * p_m; // Указатель на матрицу смежности

list * p_l; // Указатель на список смежности

unsigned long maxE; // Максимальное количество рёбер

public:

NeOrGraph(int V, int E):_e(0),_v(V),p_m(NULL),p_l(NULL),maxE(0)

{if(V<=0 || E<0) throw V;

int i=0;

for(i=1;i<V;i++)maxE+=i; // Подсчёт максимального количества рёбер

if(E>(long)maxE)throw maxE; // Если требуемое количество больше макс. - исключение

double K=2*(double)E/(double)V; // Подсчет коэффициента. насыщенности

if( K < 0.5*(V-1) )

{p_l=new list(V);}

else {p_m=new matrix(V);}

}

virtual ~NeOrGraph()

{if(p_m!=NULL)delete p_m;

if(p_l!=NULL)delete p_l;

}

//- количество вершин

inline long V(){return _v;}

//- количество рёбер

inline long E(){return _e;}

//- тип графа

virtual inline long Directed(){return 0;}

//- вставка ребра, соединяющего v1 и v2

virtual long Insert(int v1, int v2)

{if(v1 <0 || v2<0 || v1>=_v || v2>=_v)return -1;

if( v1==v2)return -2;

if( Edge(v1,v2)!=false )return 1;

if(p_m!=NULL)

{p_m->put(v1,v2,0);

if(Directed()==0)

p_m->put(v2,v1,0);

_e++;

}

if(p_l!=NULL)

{p_l->put(v1,v2,0);

if(Directed()==0)

p_l->put(v2,v1,0);

_e++;

}

return 0;

}

//- удаление ребра, соединяющего v1 и v2

long Delete(int v1, int v2)

{if(v1 <0 || v2<0 || v1>=_v || v2>=_v)return -1;

if( v1==v2)return -2;

if( Edge(v1,v2)==false )return 1;

if(p_m!=NULL)

{p_m->put(v1,v2,INT_MAX);

if(Directed()==0)

p_m->put(v2,v1,INT_MAX);

}

if(p_l!=NULL)

{p_l->put(v1,v2,INT_MAX);

if(Directed()==0)

p_l->put(v2,v1,INT_MAX);

}

_e--;

return 0;

}

//- опрос наличия ребра соединяющего v1 и v2

bool Edge(int v1, int v2)

{

if( p_m!=NULL && p_m->get(v1,v2)==INT_MAX )return false;

if( p_l!=NULL && p_l->get(v1,v2)==INT_MAX )return false;

return true;

}

//- Получить вес ребра

long getW(int v1,int v2)

{if( p_m!=NULL )return p_m->get(v1,v2);

if( p_l!=NULL )return p_l->get(v1,v2);

throw v1;

}

//- Итератор

void Iterator(int v)

{if( p_m!=NULL )p_m->iterator(v);

if( p_l!=NULL )p_l->iterator(v);

}

//- Первая вершина

long IteratorBeg()

{if( p_m!=NULL )return p_m->beg();

if( p_l!=NULL )return p_l->beg();

throw p_m;

}

//- Следующая вершина

long IteratorNext()

{if( p_m!=NULL )return p_m->next();

if( p_l!=NULL )return p_l->next();

throw p_m;

}

//- конечная вершина

long IteratorEnd()

{if( p_m!=NULL )return p_m->end();

if( p_l!=NULL )return p_l->end();

throw p_m;

}

private:

bool DFS_Visit(int v)

{cc[v]=RGB(200,200,200);bool res=false;

dd[v]=ttime++;

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

{if( Edge(v, i)!=false && cc[i]==attr )

{pp[i]=v;

DFS_Visit(i);

if( _v<10 )

{ww->put(v, i,0);ww->put(i, v,0);res=true;}

}

}

cc[v]=RGB(100,100,100);

tt[v]=ttime++;

return res;

}

public:

bool DFS(int v)

{if(v<0 || v>=_v)return false;

if(cc[v]==attr) DFS_Visit(v);

return true;

}

bool BFS(int v) // Инициализация структур возложена на управляющую программу

{if(v<0 || v>=_v)return false;

if(dd[v]!=INT_MAX)return true;

CFIFO <int> q(_v*(_v-1));

cc[v]=RGB(200,200,200);

dd[v]=0;

q. Add(v); int tmp, temp;

while(q. GetCount()!=0)

{q. Get(tmp);

for(Iterator(tmp);(temp=IteratorNext())!=-1;)

{if(cc[temp]==attr)

{cc[temp]=RGB(200,200,200);

dd[temp]=dd[tmp]+1;

pp[temp]=tmp;

q. Add(temp);

if(_v<10){ww->put(tmp, temp,0);ww->put(temp, tmp,0);}

}

}

cc[tmp]=RGB(100,100,100);

}

return true;

}

//- количество смежных вершин

long GetNumEdge(int v)

{if(p_m!=NULL)return p_m->GetNumEdge(v);

if(p_l!=NULL)return p_l->GetNumEdge(v);

throw v;

}

void Show(CDC*dc, RECT r)

{ if(_v==0)return;

if(_v>=10)

{CString cs="В графе >= 10 вершин";dc->TextOut(50,50,cs);return;}

CPoint cp( (r. left+r. right)/2, (r. top+r. bottom)/2 );

dc->SetBkMode(TRANSPARENT);

CPoint newcp=deg2coord(cp,100,0);

int i;

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

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

printE(i, j,dc, cp);

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

{newcp=deg2coord(cp, RADIUS,(short)(i*((double)360/(double)_v)));

printV(i, dc, newcp. x,newcp. y);

}

}

protected:

void arrow(int x1,int y1,int x2,int y2,CDC*dc)// Прорисовка стрелочки для ориентированных графов

{ if(x1==x2)x1++; // Чтобы не было ошибки

double dl=sqrt(pow(x2-x1,2)+pow(y2-y1,2));

double x_0=x1*16/dl+x2*(dl-16)/dl;

double y_0=y1*16/dl+y2*(dl-16)/dl;

double x_2=x1*32/dl+x2*(dl-32)/dl;

double y_2=y1*32/dl+y2*(dl-32)/dl;

double k=(y_0-(y_2*x_0-y_0*x_2)/(x_0-x_2))/x_0;

double dln=sqrt(1+pow(k,2));

double xn_1=x_0+(x_2-x_0)+(k/dln)*4;

double yn_1=y_0+(y_2-y_0)-(1/dln)*4;

double xn_2=x_0+(x_2-x_0)-(k/dln)*4;

double yn_2=y_0+(y_2-y_0)+(1/dln)*4;

dc->MoveTo((int)x_0,(int)y_0);

dc->LineTo((int)xn_1,(int)yn_1);

dc->MoveTo((int)x_0,(int)y_0);

dc->LineTo((int)xn_2,(int)yn_2);

}

virtual void printV(int v, CDC*dc, int x, int y)

{COLORREF color=cc[v];//RGB(255,200,200);

CBrush cb,*cbb;

cb. CreateSolidBrush(color);

// dc->SetBkMode(TRANSPARENT);

// dc->SetBkColor(RGB(0,255,0));

cbb=dc->SelectObject(&cb);

// dc->SetBkColor(RGB(0,255,0));

dc->Ellipse(x-15,y-15, x+15,y+15);

CString cs; cs='0'+(v%10);

dc->TextOut(x-4,y-8,cs);

if(dd!=NULL)

{cs="D="; char str[15];

if(dd[v]!=INT_MAX)

cs+=_itoa(dd[v],str,10);

else cs+="*";

if(tt!=NULL && tt[v]!=INT_MAX)

{cs+="/"; cs+=_itoa(tt[v],str,10);}

else if(tt!=NULL) {cs+="/"; cs+="*";}

dc->TextOut(x-25,y-30,cs);

}

dc->SelectObject(cbb);

}

protected:

virtual void printE(int v1, int v2, CDC*dc, CPoint center)

{if(p_m!=NULL)

{if( p_m->get(v1,v2)==INT_MAX )return; }

if(p_l!=NULL)

{if( p_l->get(v1,v2)==INT_MAX )return; }

CPoint cp1=deg2coord(center, RADIUS,(short)(v1*((double)360/(double)_v)) );

CPoint cp2=deg2coord(center, RADIUS,(short)(v2*((double)360/(double)_v)) );

CPen cp,*cpp;

cp. CreatePen(PS_SOLID, 3 , RGB(0,0,0));

if(ww->get(v1,v2)!=INT_MAX)

{cpp=dc->SelectObject(&cp);}

if(Edge(v2,v1)==false || v1<v2)

{

dc->MoveTo(cp1);

dc->LineTo(cp2);

}

if(Directed()!=0 && Edge(v1,v2)!=false)arrow(cp1.x, cp1.y, cp2.x, cp2.y, dc);

// if(Directed()!=0 && Edge(v2,v1)!=false)arrow(cp2.x, cp2.y, cp1.x, cp1.y, dc);

if(ww->get(v1,v2)!=INT_MAX)

{dc->SelectObject(cpp);}

if(Directed()==2) // Прорисовка весов рёбер

{CFont f,*tf;

f. CreatePointFont(80,"Arial",dc);

// dc->SetBkMode(OPAQUE);

tf=dc->SelectObject(&f);

char buf[10];

if(p_m!=NULL)itoa(p_m->get(v1,v2),buf,10);

if(p_l!=NULL)itoa(p_l->get(v1,v2),buf,10);

int x=(int)(cp1.x+(cp2.x-cp1.x)*0.6-5);

int y=(int)(cp1.y+(cp2.y-cp1.y)*0.6-5);

dc->TextOut(x, y+5,buf);

dc->SelectObject(tf);

}

}

bool Relax(int u, int v)

{

if (dd[u]+getW(u, v)<dd[v])

{

dd[v]=dd[u]+getW(u, v);

pp[v]=u;

return true;

}

return false;

}

public:

bool Bell_Ford(int v)

{ int i, j,val;dd[v]=0;

for(j=0;j<V();j++)

{

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

{//определяем кратчайшие пути из v во все другие вершины

ViewV++;

Iterator(i);

while( (val=IteratorNext())!=-1 )

{//релаксация всех вершин

ViewE++;

if(val==v) continue;

if(dd[i]!=INT_MAX) Relax(i, val);

}

}

}

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

{//Определяем, есть ли отрицательный цикл

ViewV++;

Iterator(i);

while( (val=IteratorNext())!=-1 )

{ViewE++;

if(val==v) continue;

if(Edge(i, val))//если есть ребро

if(dd[val]>(dd[i]+getW(i, val))) return false;

//если старый петь больше чем овый то - цикл есть

}

}

return true;

}}//- Тестирование без отображения

private:

void work_func1(int v) // Аналог DFS_Visit

{cc[v]=1;

// dd[v]=ttime++;

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

{if(Edge(v, i)!=false)

ViewEdge++;

if( Edge(v, i)!=false && cc[i]==0 )

{work_func1(i);

}

}

cc[v]=2;

// tt[v]=ttime++;

}

public:

void Task1()

{for(int i=0;i<_v;i++,ViewEdge++)

if(cc[i]==0){work_func1(i);}

}

//- Тестирование без отображения

private:

void work_func2(int v) // Аналог DFS_Visit

{cc[v]=1;

// dd[v]=ttime++;

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

{if(Edge(v, i)!=false)

ViewEdge++;

if( Edge(v, i)!=false && cc[i]==0 )

{work_func2(i);

}

if( Edge(v, i)!=false && cc[i]!=0 && cc[i]!=2 )

{ViewEdge--;Delete(v, i); // Преобразование в ациклический, с уменьшением статистики

}

}

cc[v]=2;

// tt[v]=ttime++;

}

public:

void Task2()

{for(int i=0;i<_v;i++,ViewEdge++)

if(cc[i]==0){work_func2(i);}

}

//- Тестирование без отображения

void Task3(int v)

{dd[v]=0;

CFIFO_Prior cfp(_v);

for(int i=0,u, d;i<V();i++)

{cfp. Add(i, dd[i]);}

while(cfp. GetCount()!=0)

{cfp. Get(u, d);ViewEdge++;

for(Iterator(u);(i=IteratorNext())!=-1;)

{ViewEdge++;

if( cfp. Search(i)!=false && dd[i] > (dd[u]+getW(u, i)) )

{dd[i]=dd[u]+getW(u, i);

// pp[i]=u;

cfp. Set(i, dd[i]);

}

}

}

}

};

class OrGraph:public NeOrGraph

{public:

OrGraph(int V, int E):NeOrGraph(V, E/2)

{

}

~OrGraph()

{

}

//- тип графа

virtual inline long Directed(){return 1;}

public:

};

class VOrGraph:public OrGraph

{public:

//- тип графа

virtual inline long Directed(){return 2;}

VOrGraph(int V, int E):OrGraph(V, E)

{

}

~VOrGraph()

{

}

//- вставка ребра, соединяющего v1 и v2 с весом w

virtual long Insert(int v1, int v2, int w)

{if(v1 <0 || v2<0 || v1>=_v || v2>=_v)return -1;

if( v1==v2)return -2;

if(p_m!=NULL) {p_m->put(v1,v2,w);}

if(p_l!=NULL) {p_l->put(v1,v2,w);}

_e++;

return 0;

}

};

Вызывающие функции (ответственные за инициализацию):

void CRGRDlg::OnDfsButton()

{

UpdateData(true);

OnClearButton();

pp=new int[p_g->V()];

dd=new unsigned int[p_g->V()];

tt=new int[p_g->V()];

ttime=1;

for(int i=0;i<p_g->V();i++)

{cc[i]=attr; // Сбросить до исходных цветов

pp[i]=-1;

dd[i]=INT_MAX;

tt[i]=INT_MAX;}

void CRGRDlg::OnBfsButton()

{

UpdateData(true);

OnClearButton();

pp=new int[p_g->V()];

dd=new unsigned int[p_g->V()];

for(int i=0;i<p_g->V();i++)

{cc[i]=attr; /// Сбросить до исходных цветов

pp[i]=-1;

dd[i]=INT_MAX;

}

if( p_g->BFS(m_v_fs)==false )MessageBox("Начальная вершина не существует","ОШИБКА",MB_ICONERROR);

if( m_full_fs==false )return;

for(i=0;i<p_g->V();i++)

if(dd[i]==INT_MAX) p_g->BFS(i);

InvalidateRect(&r_paint);

}

void CRGRDlg::OnTask1Button()

{

OnClearButton();

pp=new int[p_g->V()];

dd=new unsigned int[p_g->V()];

for(int i=0;i<p_g->V();i++)

{cc[i]=attr; /// Сбросить до исходных цветов

pp[i]=-1;

dd[i]=INT_MAX;

}

for(int j=0;j<p_g->V();j++)

{if(cc[j]==attr)p_g->BFS(j);}

for(i=0,j=0;i<p_g->V();i++)

{if(dd[i] > (unsigned)j) j=dd[i];}

CString cs;cs. Format("Диаметр графа: %i",j);

MessageBox(cs);

OnClearButton();

InvalidateRect(&r_paint);

}

void CRGRDlg::OnTask2Button()

{

OnClearButton();

if(!UpdateData(true) || m_v_task3>=p_g->V()){MessageBox("ОШИБКА");return;};

pp=new int[p_g->V()];

dd=new unsigned int[p_g->V()];

tt=new int[p_g->V()]; ttime=1;

for(int i=0;i<p_g->V();i++)

{cc[i]=attr; /// Сбросить до исходных цветов

pp[i]=-1;

dd[i]=INT_MAX;

tt[i]=INT_MAX;

}

p_g->DFS(m_v_task3);cc[m_v_task3]=RGB(0,240,0);

for(i=0;i<p_g->V();i++)

{if(cc[i]==RGB(100,100,100))cc[i]=RGB(200,240,100);

}

delete dd;dd=NULL;

delete pp;pp=NULL;

InvalidateRect(&r_paint);

}

void CRGRDlg::OnTask3Button()

{

UpdateData(true);

if(m_v_task3>=p_g->V())

{MessageBox("Начальная вершина не существует!","Ошибка:",MB_ICONERROR);}

OnClearButton();

pp=new int[p_g->V()];

dd=new unsigned int[p_g->V()];

for(int i=0;i<p_g->V();i++)

{cc[i]=attr; /// Сбросить до исходных цветов

pp[i]=-1;

dd[i]=INT_MAX;

}

if( !p_g->Bell_Ford(m_v_task3) ){MessageBox("В графе присутствует отрицательный цикл!"); OnClearButton(); return;}

else

{CString cs;

int nT, i;

int nVmax=p_g->V();

cs. Format("Кратчайший путь от вершины %d до:\r\n",m_v_task3);

CString str, str1,str2;

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

{

if(i==m_v_task3) continue;

if(pp[i]==-1) str. Format("(%d): нет пути!",i);

else

{

str. Format("(%d): %d",i, m_v_task3);

str2="";

nT=i;

while(nT!=m_v_task3)

{

str1.Format(" - %d",nT);

str2=str1+str2;

nT=pp[nT];

}

str+=str2;

str1.Format(". Вес пути: %d.",dd[i]);

str+=str1;

}

str+="\r\n";

cs+=str;

}

MessageBox(cs);

}

OnClearButton();

}