Исследование алгоритмов топологической сортировки
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?у
Процедура возвращает true, если граф был топологически отсортирован, иначе возвращается false. - массив, в котором хранятся цвета вершин (0 - белый, 1 - серый, 2 - черный).- количество вершин.- массив списков смежных вершин.- массив, в котором сохраняются новые номера вершин.- стек, в котором складываются вершины после их обработки.- принимает значение true, если в графе найден цикл.
1 boolean topological_sort(){
boolean Cycle;
for(int i = 1;i <= N;i ++){
Cycle = dfs(i);
if(Cycle)return false;
}
for(int i = 1;i <= n;i ++){
Numbers[Stack.pop()] = i;
}
return true;
}
boolean dfs(int v){
if(Color[v] == 1)return true;
if(Color[v] == 2)return false;
Color[v] = 1;
for(int i = 0;i < Edges[v].size();i ++){
if(dfs(Edges[v].get(i)))return true;
}
Stack.push(v);
Color[v] = 2;
21 return false;
}
Комментарий
-6. Вызывается обход в глубину от всех вершин. Заканчиваем работу алгоритма, если обнаружен цикл.
-9. Заносим в массив новые номера вершин.
-14. Если вершина серая, то мы обнаружили цикл. Заканчиваем поиск в глубину.
. Если вершина черная, то заканчиваем ее обработку.
. Красим вершину в серый цвет.
-18. Обрабатываем список смежных с ней вершин.
. Кладем вершину в стек.
. Красим вершину в черный цвет.
3.3 Вывод
Были реализованы основные алгоритмы топологической сортировки в программной среде. Проведен анализ каждого из этапов разработки данных алгоритмов, также были приведены результаты.
ЗАКЛЮЧЕНИЕ
Топологическая сортировка - это сортировка элементов, для которых определён частичный порядок, то есть упорядочение задано не на всех, а только на некоторых парах элементов. Кроме того, она является одним из основных алгоритмов на графах, который применяется для решения более сложных задач.
В данной курсовой работе были рассмотрены общие принципы топологической сортировки, изучены основные методы топологической сортировки, а также их реализация в различных программных средах. Из проделанной работы можно сделать следующие выводы:
Топологическая сортировка применима в разных отраслях:
сети;
создание карты сайта;
календарное планирование и т.д.
Алгоритмы топологической сортировки достаточно просты и понятны, также легко реализуемы в программной среде.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
.Кнут Д. Искусство программирования Т. 1. Основные алгоритмы. - М.: Вильямс, 2000, - 736с.
.Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1983,-406с.
.Кофман А., Фор Р. Займемся исследованием операций. - М.: Мир, 1966, - 262с.
.Кнут Д. Искусство программирования Т. 3. Сортировка и поиск. - М.: Вильямс, 2000.
.Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.:Вильямс, 2000 - 384 с.
.Окулов С.М. Программирование в алгоритмах. М.: Лаборатория базовых знаний, 2002.-341 с.
.Седжвик Р. Фундаментальные алгоритмы на С++/Алгоритмы на графах- К.:Диасофт, 2002. - 496 с.
.Седжвик Р. Фундаментальные алгоритмы на С++/Анализ/Структуры данных/Сортировка/Поиск - К.:Диасофт, 2001. - 688с.
.Бакнелл Дж. Фундаментальные алгоритмы и структуры данных в Delphi. - СПб.: Диасофт, 2003. - 560 с.
.Белоусов А.И., Ткачев С.Б., Дискретная математика Москва, 2004 - 743с.
Приложение 1
#include "stdafx.h"
#include
namespace std;struct Leader *Lref; //Тип: указатель на заголовочный узел.
typedef struct Trailer *Tref; //Тип: указатель на дуговой узел.
//Описание типа заголовочного узла.
typedef struct Leader
{
int Key; //Информационное поле.
int Count; //Количество предшественников.
Tref Trail;
Lref Next;
};
топологический сортировка сайт древовидный
//Описание типа дугового узла.
typedef struct Trailer
{
Lref Id;
Tref Next;
};
Spisok {
private:
Lref Head; //Указатель на список заголовочных узлов.
Lref Tail; //Указатель на фиктивный элемент
//в конце списка заголовочных узлов.
int z; //Количество узлов, не имеющих предшественников.
public:
Spisok () {//Инициализация списка заголовочных узлов.
Head = Tail = new (Leader); z = 0;};
Lref L (int);
void Poisk();
void Vyvod();
};
Spisok::Poisk()
{
Lref p,q; // Рабочие указатели.
p = Head; Head = NULL;
while (p!=Tail)
{
q = p; p = p->Next;
if (q->Count==0)
{ q->Next = Head; Head = q; }
}
}
Spisok::L (int w)
//Функция возвращает указатель на ведущего с ключом w.
{
Lref h = Head;
Tail->Key = w;
while (h->Key!=w) h = h->Next;
if (h==Tail)
// В списке нет элемента с ключом w.
{
Tail = new (Leader); z++;
h->Count = 0; h->Trail = NULL; h->Next = Tail;
}
return h;
}
Spisok::Vyvod()
{
Lref p,q; // Рабочие указатели.
Tref t;
cout << endl;
cout << "Результат...\n";
q = Head;
while ( q!=NULL)
{
cout Key << " ";
z--;
t = q->Trail; q = q->Next;
while (t!=NULL)
{
p = t->Id; p->Count--;
if (p->Count==0) // Включение (*p) в список ведущих.
{ p->Next = q; q = p; }
t = t->Next;
}
}
if (z!=0)
cout << "\nМножество не является частично упорядоченным!\n";
}
main()
{
{setlocale (LC_ALL, "Russian");}
Spisok A;
Lref p,q; // Рабочие указатели.
Tref t;
int x,y; // Рабочие переменные.
// Фаза ввода.
cout << "Задайте отношение частичного порядка...\n";
cout << "Элемент ";
cin >> x;
cout << " предшествует элементу ";
while (x!=0)
{
cin >> y;
p = A.L(x); q = A.L(y);
t = new (Trailer); t->Id = q; t->Next = p->Trail;
p->Trail = t; q->Count += 1;
cout << "Элемент ";
cin >> x;
cout << " предшествует элементу ";
}
// Поиск ведущих с нулевым количеством предшественников.
A.Poisk();
// Фаза вывода.
A.Vyvod();
}