Реализация алгоритма нахождения множеств элементарных циклов графа средствами языка С++

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Содержание

Введение

Некоторые сведения из теории графов

Способы представления графа в информатике

Поиск в глубину множества элементарных циклов графа

О среде wxDev-C++

Разработка в wxDev-C++

Руководство пользователю

Заключение

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

Приложение А

Введение

В настоящее время дискретная математика и смежные с ней разделы привлекают большое внимание специалистов различных областей науки и техники, являясь эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Особое значение с практической точки зрения имеет теория графов, использующаяся при проектировании интегральных схем и схем управления, исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, при разработке вычислительных и информационных сетей, в схемотехническом и конструкторско-топологическом проектировании, и т.д. Обширное применение теория графов находит в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании ЭВМ, баз данных, систем логического управления. Поэтому основное внимание в курсовой работе уделяется изложению основ теории графов и алгоритмов поиска элементарных циклов в глубину в неориентированных графах.

Некоторые сведения из теории графов

В теории графов объекты представляются как вершиныграфа, а связи -- как дуги, или рёбра. Граф или неориентированный графG(рис.1) -- это упорядоченная параG: = (V,E), для которой выполнены следующие условия: V это непустое множество вершин , E это множество пар (в случае неориентированного графа -- неупорядоченных) вершин, называемых рёбрами.

Рисунок 1 Неориентированный граф

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | -- порядком, число рёбер | E | -- размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

Ориентированный граф (сокращённо орграф) G(рис.2) -- это упорядоченная параG: = (V,A), для которой выполнены следующие условия: V это непустое множество вершин или узлов, A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Рисунок 2 Ориентированный граф

Дуга -- это упорядоченная пара вершин (v, w), где вершину v называют началом, а w -- концом дуги. Можно сказать, что дуга ведёт от вершины v к вершине w.

Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.

Ориентированным путём в орграфе называют конечную последовательность вершин vi, для которой все пары (vi,vi + 1)являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что, всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины. Всякий простой неэлементарный путь содержит элементарный цикл. Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро). Петля -- элементарный цикл.

Граф с петлями и кратными ребрами (дугами) называется псевдографом. Граф с кратными ребрами (дугами) и без петель называется мультиграфом.

Граф, не содержащий петель и кратных ребер, называется простым графом.

Две вершины графа xi и хj называются смежными, если существует соединяющее их ребро (дуга). Два ребра (дуги) смежны, если они имеют общую вершину

Множество вершин графа называется независимым, если никакие две вершины этого множества не соединены ребром. Другими словами, индуцированный этим множеством подграф состоит из изолированных вершин. Иногда также говорят, что каждое ребро графа инцидентно не более чем одной вершине из независимого множества.

Способы представления графа в информатике

Матрица смежности. Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин, двумерный массив; матрица с пропусками; неявное задание (при помощи функции).

Матрица инцидентности. Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается: 1в случае, если связь j «выходит» из вершины i,?1,если связь «входит» в вершину,0 во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким (размер пропорционален | E | | V | ) для хранения, но облегчает нахождение циклов в графе.

Список рёбер -- это тип представления графа в памяти компьютерной программы, подразумевающий, что каждое ребро представляется двумя числами -- номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.

Поиск в глубину множества элементарных циклов графа

Поиск в глубину (англ. Depth-firstsearch, DFS) -- один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.

Пусть задан графG = (V,E), где V -- множество вершин графа, E -- множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

Из множества всех белых вершин выберем любую вершину, обозначим её v1.

Выполняем для неё процедуру DFS(v1).

Перекрашиваем её в чёрный цвет.

Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр -- вершина )

Перекрашиваем вершину u в серый цвет.

Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).

Окрашиваем w в чёрный цвет.

Данный алгоритм поиска используется и в моей программе, а в руководстве пользователю я описал, как пользоваться моей программой и далее привел пример.

О среде wxDev-C++

Я разрабатывал данный программный продукт в среде wxDev-С++.

wxDev-C++ является развитием проекта Dev-C++, но также содержит дизайнер форм для библиотеки разработки wxWidgets. WxDev-C++ включает все свойства Dev-C++, а также новейшую версию wxWidgets необходимую дизайнеру форм для среды быстрой разработки приложений .

Родитель wxDev-C++ - это Dev-C++. Dev-C++ -- свободная интегрированная среда разработки приложений для языков программирования C/C++. В дистрибутив входит компилятор MinGW. Сам Dev-C++ написан на Delphi. Распространяется согласно GPL.

Проект поддерживается SourceForge. Основатель проекта Колин Лаплас, компания Bloodshed Software.

Одно время был доступен Linux-порт, однако на настоящее время актуализирована только Windows-версия.

Разработка в wxDev-C++

Что бы приступить к работе в wxDev-C++ необходимо запустить среду.

Далее в левом верхнем углу выбрать файл (рис 6).

Рисунок 6 меню wxDev-C++

Файл>Создать>Проект (рис7)

Рисунок 7 Как создать проект в wxDev-C++

Далее в открывшемся окне выбрать тип проекта и задать название(рис8).

Рисунок 8 создание проекта

В моем случае тип проекта - Console Application название h1.

Далее необходимо задать расположение проекта на компьютере.

В моем случае (рис9) это G:\Курсовая работа по дис.мат\

Рисунок 9 расположение проекта

И нажать кнопку сохранить. Далее в открывшемся поле редактора кода видим предварительно скомпонованный заголовок(рис10) из нескольких стандартных библиотек и главной функции main, с которой начинается выполнение программы.

Рисунок 10 Редактор кода wxDev-C++

Сам код моей программы в Приложении А.

Руководство пользователю

Моя программа ищет и выводит на экран простые циклы. Она очень проста в использовании. Запустив , ее вы поймете это сами.

Итак, запустили, программа просит нас ввести количество ребер в графе(рис3). Вводим, например 4.

Далее необходимо ввести ребра, поочередно одну и вторую вершину каждого ребра(рис4).

Рисунок 3 первое, что видим после запуска программы

граф алгоритм цикл программа

Рисунок 4 вводим ребра графа

Далее увидим результат - матрицу смежности и элементарный цикл, которые программа выведет на экран в этом же окне(рис5).

Рисунок 5 результат работы программы.

Заключение

Современное состояние и тенденции развития вычислительной техники как основного инструмента информатики таковы, что наряду с увеличением функциональности вычислительная техника приобретает свойства, позволяющие работать на ней пользователю, не разбирающемуся в программировании. В этот период появился более качественный интерфейс программ. Появились структуры графических данных и более крупные, интегральные информационные единицы - объекты. Следствием стало бурное развитие объектно-ориентированных систем программирования, таких как Visual C++, Visual BASIC и других, в основе которых лежит обработка объектных структур данных. Также появились новые языки программирования ADA, OCCAM.([3]) И если раньше большой популярностью пользовались простые линейные алгоритмы то в настоящее время алгоритмы таких типов как деревья, графы, списки, очереди - получают все большее распространение.

Названные алгоритмы могут найти свои применения в программах для транспортных и коммуникационных сетей, таких как: железнодорожной транспортной сети, где вершины - станции, связи - дороги, таксомоторная сеть: вершины - места стоянки автомобилей, связи - пути подъезда; перемещение потока вещества по системе труб в определенный пункт назначения и т.д. На основе алгоритма поиска в ширину в графе можно построить программу вывода дерева наименьшей стоимости, что позволит рассчитывать кратчайшие пути к определенному месту назначения (вершине).

Таким образом, развитие информационных технологий, их проникновение во все области жизнедеятельности человека требуют компьютерного отображения информации в виде соответствующих структур данных. И графы, являясь одной из частей этих структур данных, играют важную роль в современном программировании, графы встречаются в сотнях разных задач.

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

1.Судоплатов С.В. Математическая логика и теория алгоритмов: учебник / С.В. Судоплатов, Е.В. Овчинникова. М.: ИНФРА-М, 2004. - 224 с.

2. Иванов Б.Н. Дискретная математика. Алгоритмы и программы / Б.Н. Иванов. М.: Лаборатория базовых знаний, 2003. - 288 с.

3. Кристофиес П. Теория графов. М.: ИНФРА-М, 2004. - 328 с.

Приложение А

//////////////////////////////////////////////////////////////////////////////////////

//Дана матрица смежности неориентированного графа. Найти множество элементарных циклов

//графа (используется алгоритм поиска в глубину)

//////////////////////////////////////////////////////////////////////////////////////

#include <algorithm>

#include <deque>

#include <iostream>

#include <map>

#include <set>

#include <string>

#include <vector>

//////////////////////////////////////////////////////////////////////////////////////

using namespace std;

/*создаем новые типы переменных и обзываем */

typedef string T_vertice;

typedef set<T_vertice> T_vertices_set; //set<T_vertice> - множество вершин

typedef vector<T_vertice> T_vertices;

typedef T_vertices_set T_edge;

typedef set<T_edge> T_edges;

typedef map<T_vertice, bool> T_row;

typedef map<T_vertice, T_row> T_matr;

typedef map<T_vertice, int> T_vertice_time;

//////////////////////////////////////////////////////////////////////////////////////

/*функция вывода на экран матриц смежности*/

void print_matr(T_matr& matr, const T_vertices& vertices)

{

for(T_vertices::const_iterator vertice_row_it = vertices.begin();

vertice_row_it != vertices.end(); ++vertice_row_it)

{

for(T_vertices::const_iterator vertice_col_it = vertices.begin();

vertice_col_it != vertices.end(); ++vertice_col_it)

{

cout<< '\t'

<< matr[*vertice_row_it][*vertice_col_it];

}

std::cout <<endl

<<endl

<<endl;

}

}

//////////////////////////////////////////////////////////////////////////////////////

/*ввод вершин*/

T_vertices get_vertices(const T_edges& edges)

{

T_vertices_set vertices_set;

for(T_edges::const_iterator edge_it = edges.begin(); edge_it != edges.end();

++ edge_it)

{

vertices_set.insert(*edge_it->begin());

vertices_set.insert(*edge_it->rbegin());

}

return T_vertices(vertices_set.begin(), vertices_set.end());

}

//////////////////////////////////////////////////////////////////////////////////////

/*получение матрицы смежности*/

T_matr get_adjacency_matr(const T_edges& edges)

{

T_matr adjacency_matr;

for(T_edges::const_iterator edge_it = edges.begin(); edge_it != edges.end();

++ edge_it)

{

T_vertice v1 = *edge_it->begin();

T_vertice v2 = *edge_it->rbegin();

adjacency_matr[v1][v2] = adjacency_matr[v2][v1] = true;

}

return adjacency_matr;

}

//////////////////////////////////////////////////////////////////////////////////////

/*элементарные циклы*/

void print_cycles

(

const T_vertices vertices,

T_matr& adjacency_matr,

T_vertices& spanning_tree,

T_vertice_time& vertice_time,

int& time,

T_vertice vertice_U

)

{

spanning_tree.push_back(vertice_U);

vertice_time[vertice_U] = ++time;

for(T_vertices::const_iterator vertice_V_it = vertices.begin();

vertice_V_it != vertices.end(); ++vertice_V_it)

{

if(adjacency_matr[vertice_U][*vertice_V_it])

{

if(vertice_time[*vertice_V_it] == 0)

{

print_cycles

(

vertices,

adjacency_matr,

spanning_tree,

vertice_time,

time,

*vertice_V_it

);

}

else

{

if(*vertice_V_it != *(spanning_tree.rbegin() + 1)

&& vertice_time[*vertice_V_it] < vertice_time[vertice_U])

{

std::cout << "Elementarnii tsikl: "

<< std::endl;

for(T_vertices::const_iterator

tree_vertice_it

= std::find(spanning_tree.begin(), spanning_tree.end(), *vertice_V_it);

tree_vertice_it != spanning_tree.end(); ++tree_vertice_it)

{

std::cout << *tree_vertice_it

<< std::endl;

}

std::cout << std::endl;

}

}

}

}

}

//////////////////////////////////////////////////////////////////////////////////////

int main()

{

setlocale(0,"Rus");

locale::global(locale(""));

int n = 0;

do

{

cout << "Vvedite kolichestvo reber neorintirovannogo grafa:";

cin >> n;

}while(n <= 0);

cout << "Vvedite rebra neorintirovannogo grafa"

"(vershini v rebre ne dolzhni sovpadat t.e. bez petel):";

T_edges edges;

do

{

cout << endl

<< "rebro #"

<< edges.size() + 1

<< ":"

<< endl

<< "\t-> ";

T_vertice v1;

cin >> v1;

T_edge edge_cur;

edge_cur.insert(v1);

T_vertice v2;

cout << "\t-> ";

cin >> v2;

edge_cur.insert(v2);

if(edge_cur.size() == 2)

{

edges.insert(edge_cur);

}

}while(static_cast<int>(edges.size()) < n);

T_vertices vertices = get_vertices(edges);

T_matr adjacency_matr = get_adjacency_matr(edges);

cout << "Matritsa smezhnosti grafa:"

<< std::endl;

print_matr(adjacency_matr, vertices);

T_vertices spanning_tree;

T_vertice_time vertice_time;

int time = 0;

print_cycles

(

vertices,

adjacency_matr,

spanning_tree,

vertice_time,

time,

vertices.front()

);

system("PAUSE");

}

Размещено на www.allbest.