Программная реализация алгоритмов поиска в глубину и ширину в неориентированных графах

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

Рубрика Экономико-математическое моделирование
Вид курсовая работа
Язык русский
Дата добавления 15.03.2011
Размер файла 687,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

20

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

Введение

программа граф ориентированный пользователь

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

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

1. Теоретическая часть

1.1 Основы теории графов

1.1.1 Ориентированные и неориентированные графы

Графом G=(X, U) будем называть совокупность двух конечных множеств: множества вершин X={x1,…, xn} и множества ребер (дуг)

U = {u1…..um}, состоящего из некоторых пар элементов (xi, xj) множества X.

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

Если пары вершин (xi, xj) в множестве U являются неупорядоченными (т.е., порядок соединения вершин несущественен), то граф называется неориентированным (неорграфом), а пары (xi, xj) - ребрами этого графа (рис. 1, а). При этом вершины xi, xj называют концами (концевыми вершинами) ребра. В данном случае также говорят, что ребро (хi, xj,) соединяет вершины xi и xj. Если пары вершин (xi, xj) в множестве U являются упорядоченными (т.е., порядок соединения вершин существенен), то граф называется ориентированным (орграфом), а пары (xi, xj) - дугами. Дуги орграфа, в отличие от ребер неорграфа, будем обозначать < xi, xj >. При этом xi - начало (начальная вершина) дуги, xj - конец (конечная вершина) дуги. Говорят также, что дуга < xi, xj > исходит из вершины xi и заходит в вершину xj. Заметим, что < xi, xj > и < xi, xj > - это различные дуги в графе. При изображении орграфа дуги обозначают стрелками, указывающими их ориентацию (направление). Графы, в которых имеются и неориентированные ребра, и дуги, называются смешанными. Заметим, что любой неориентированный граф может быть представлен в виде орграфа путем замены каждого его ребра двумя противоположно направленными дугами.

В дальнейшем вершины графа будем обозначать символами х1, х2,…, ребра - символами u1, u2,… (или парами (xi, xj)), дуги - символами u1, u2,… (или упорядоченными парами < xi, xj >). Число вершин графа обозначим через n, число ребер (дуг) - через m.

Пара вершин xi, xj может соединяться двумя или более ребрами (дугами одного направления). Такие ребра (дуги) называют кратными. Количество одинаковых ребер (xi, xj) (дуг < xi, xj >) называется кратностью соответствующего ребра (дуги). Петлей называется дуга (ребро), с совпадающими начальной и конечной вершинами.

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

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

Так, граф, представленный на рис. 1, а является псевдографом, так как содержит петлю (xi, xj) и кратное ребро (х2, x3); граф на рис. 1, б является мультиграфом, граф на рис. 1, в-простым графом.

Две вершины графа xi и хj называются смежными, если существует соединяющее их ребро (дуга). Два ребра (дуги) смежны, если они имеют общую вершину. Вели ребро (дута) Uk соединяет вершины xi и xj. то говорят, что ребро (дуга) инциндентно вершинам xi и xj, а вершины xi и xj инциндентны ребру (дуге) Uk. Так, на рисунке 1 а вершина x5 инциндетна ребрам U6, U9, U5, ребра U10 и U6 являются смежными; смежными являются вершины х1 и х6, x5 и х6.

Рисунок 1 - Изображения графов

Часто граф задают парой (Х, Г), где X - множество вершин графа, а Г - отображение, ставящее в соответствие каждой вершине графа подмножество множества X. При этом для орграфа Г(хi) - множество вершин xj є X, для которых в графе существует дуга <хi, хj>; Г-1i) - множество вершин хk є Х, для которых в графе существует дуга <xk, xi>. Для неорграфа Г (х,)= Г-1i) и означает количество вершин, смежных с вершиной xi.

Подграфом графа G=(X, U) называется граф G'=(X'.U'), для которого X'є X, U' є U. Остовным подграфом графа G=(X, U) называется граф G0= (X, U0), содержащий все вершины графа G. Порожденным подграфом графа G=(X.H) на множестве вершин Хр называется граф Gp=(Xp, Up), где Хp є Х, а Up - множество ребер (дуг) графа G, оба конца которых принадлежат множеству Хр. Так. на рис. 2, а представлен граф G, на рис. 2, б - его произвольный подграф, на рис. 2, в-порожденный подграф графа G на множестве вершин Х {x1, x2, x3, x4} на рисунке 2, г - один из остовных подграфов графа G.

Рисунок 2 - Изображение остовного подграфа

Граф G =(X, U) называется дополнением простого графа G=(X, U), если множества вершин G и G совпадают, а две вершины смежны в G тогда и только тогда, когда они не смежны в G. На рисунке 3 представлен граф G и его дополнение.

Рисунок 3 - Изображение графа и его дополнения

Число дуг, исходящих из вершины хi, ориентирован но го графа, называется полустепенью исхода вершины хi, и обозначается р-(х,). Число дуг, заходящих в вершин xi, напивается полустепенью захода вершины xi и обозначается р+(х,). В случае ориентированного псевдографа вклад каждой петли, инциндентной некоторой вершине хi, равен 1 как в р-(xi), так и в р+(xi). Так. для орграфа, представленного на рис. 3, 6 p-(x1)=l; p+(x1)=2; р-(x2)=3; р+2)=2. Для любого орграфа выполняется равенство:

В неориентированном графе число ребер, инциндентных данной вершине xi, называется степенью (валентностью) вершины хi и обозначается р(хi). Вершина графа, имеющая степень 0, называется изолированной, а вершина, имеющая степень I - висячей. Для неориентированного псевдографа вклад каждой петли, инциндентной вершине xi, в р(хi) равен 2. Для неорграфа на рис. 3, а р(х4)=4; p(x1)=5. Число вершин нечетной степени в любом графе четно. Для любого неорграфа справедливо следующее равенство

1.1.2 Матричный способ задания графов

Матрицей смежности неориентированного графа G=(X, U) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:

Для ориентированного графа:

В псевдографе aij =k, где k - кратность ребра (xi, xj) (дуги < xi, xj >). Петлям в матрице смежности соответствуют элементы, расположенные на главной диагонали. Сумма - элементов матрицы А неорграфа G пo i - и строке (или по i - му столбцу) равна р(хi). Для орграфа сумма элементов матрицы А по i - й строке равна р-i). по i - му столбцу р+i). Очевидно, что матрица смежности неорграфа является симметричной относительно главной диагонали, Матрицей инциндентности неориентированного графа G=(X, U) с n вершинами и m ребрами называется матрица В размера n x m, элементы которой определяются следующим образом:

Для ориентированного графа:

1.1.3 Изоморфизм и гомеоморфизм графов

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

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

Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его рёбер.

1.1.4 Маршруты, цепи, циклы в графах

Последовательность ребер неорграфа (x1, x2), …, (xr-1, xr), в которой конец каждого предыдущего ребра совпадает с началом следующего, называется маршрутом, соединяющим вершины x1 и xг. Аналогом маршрута для орграфа является ориентированный маршрут из х1 в хг. представляющий собой последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей. При этом x1 и xr называются начальной и конечной вершинами маршрута. Если любые две вершины графа соединены маршрутом, то граф называется связным.

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

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

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

Если в графе имеется хотя бы одно ребро и отсутствуют висячие вершины, то этот граф содержит хотя бы один простой цикл. В псевдографах, мультиграфах и простых графах минимальная длина простою цикла равна 1, 2 и 3 соответственно.

1.1.5 Основные типы графов

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

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

Граф, у которого все вершины имеют одинаковую степень k, называется регулярным (однородным) графом степени k. Число ребер m такого графа определяется следующим образом:

Граф, не имеющий ребер, называется пустым, а его вершины - изолированными. Пустой граф, имеющий n вершин, обозначается Оn.

Граф называется полным, если все его вершины смежны. Полный граф порядка n обозначается Кn. Число ребер полною графа Кn определяется следующим образом:

Граф G=(X, U) называется двудольным, если существует такое разбиение множества его вершин X на два непересекающихся подмножества X1 и X2, что каждое ребро имеет одну концевую вершину в подмножестве X1, а другую - в надмножестве X2. Подмножества X1 и X2 в данном случае называются долями. Если две вершины графа, входящие в разные доли, смежны, то граф называется полным двудольным и обозначается Кn1,n2, где n1=|X1|, n2=|X2|. Аналогично определяются k-дольный и полный k-дольный графы (k>2). Граф является двудольным тогда и только тогда, когда он не имеет простых циклон нечетной длины.

Реберным (смежностным) графом простого графа G=(X, U) называется граф L(G)=(U, V), вершинам которою соответствуют ребра графа G, причем все вершины ui и uj графа L(G) смежны тогда и только тогда, когда смежны соответствующие им ребра ui и uj графа G.

1.1.6 Достижимость и связность

Вершина xj неорграфа (орграфа) достижима из вершины xj, если существуем маршрут, соединяющий хi и хj (путь из хi в хj). Если в орграфе существуют пути из хi в хj и обратно, то говорят, что вершины хi и хj взаимно достижимы.

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

Компонентой связности неорграфа называется его максимальный связный подграф, то есть подграф, не содержащийся ни в каком другом связном подграфе этого графа. Аналогично сильной компонентой орграфа называется его максимальный сильно связный подграф.

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

Числом вершинной связности ?(G) графа называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. Числом реберной связности ?(G) называется наименьшее число ребер, при удалении которых граф становится несвязным. ?*(G) < ?*(G) < p*(G), где p*(G) - минимальная степень вершин графа.

Вершина хi называется точкой сочленения (или разделяющей вершиной), если после ее удаления граф становится не связным. Ребро графа называется мостом, если его удаление приводит к несвязному графу.

1.1.7 Деревья

Связный ациклический граф, имеющий не менее двух вершин, называется креном. Любое дерево на n вершинах содержит n-1 ребер и имеет по крайней мере две висячие вершины. Любые две вершины дерева связаны единственной простой пенью. Ориентированным деревом называется орграф без циклов, в котором имеется вершина x0, из которой существует только один ориентированный путь в любую другую вершину. Деревом графа G называется любой его связный ациклический подграф. Дерево графа G, содержащее все вершины этого графа, называется остовным дереном (остовом) Т графа G. При этом ребра остовного дерева Т называются ветвями, а ребра графа G, не принадлежащие остову Т - хордами. К - деревом называется ациклический граф, состоящий из k компонент связности. Если k - дерево является остовным подграфом графа G, то оно называется k - остовом этого графа. Ациклический несвязный граф, все компоненты связности которого являются деревьями, называется лесом.

Очевидно, что в любом графе существует остов, причем в общем случае остов может быть выделен не единственным способом. Например, для полною графа Кn существует nn-2 остовных деревьев. Таким образом, число деревьев, которые можно построить на данных n вершинах, равно nn-2.

Для остовного дерева Т справедливы следующие утверждения:

1) Т - связный граф, но он утрачивает связность при удалении хотя бы одного ребра.

2) Т - ациклический граф, но добавление хотя бы одного ребра приводит к появлению в нем цикла.

3) Число ребер графа Т на 1 меньше числа его вершин.

1.1.8 Алгоритм поиска в глубину и ширину

Для построения произвольного остова связного графа могут быть использованы две стратегии: поиск в глубину и поиск в ширину.

Опишем алгоритм поиска в глубину (этот метод стал одной из основных методик проектирования графовых алгоритмов). Поиск начинается с некоторой фиксированной вершины x0, например, с висячей. Затем выбирается вершина x1, смежная с x0. После этого выбирается вершина х2, смежная с х1, и т.д. Еще не просмотренные вершины будем условно называть новыми. Если на k-м шаге поиска для вершины xk существует новая вершина xk+1, то она выбирается (перестаёт быть новой) и поиск продолжается от вершины xk+1. Если же для вершины xk новых вершин не существует, осуществляется возврат к вершине, из которой мы попали в xk, и поиск осуществляется от неё. Процесс продолжается до тех нор, пока не будет произведён возврат в вершину х0. В процессе поиска вершины соединяют рёбрами.

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

2. Описание программы

2.1 Описание структуры программы

Весь алгоритм программы можно разбить на следующие шаги.

1) Директива компилятора {$1-} указывает на необходимость отключить автоматическое завершение программы в случае ошибки ввода-вывода. Используется модуль crt (это позволяет применить в программе некоторые нестандартные для обычного языка Pascal процедуры и функции).

2) Объявляются переменные и метки и описываются процедуры. Следующие идентификаторы являют собой: а - 1) матрица смежности неорграфа (максимальный размер 15*15), 2) если имеются индексы, то - элемент матрицы смежности; b - 1) массив новых вершин неорграфа, 2) если есть индекс, то - свойство вершины («1» - новая, не просмотренная вершина, «0» - старая, уже просмотренная); с - 1) «очередь / стек» (массив), 2) если есть индекс, то - элемент «очереди / стека»; i - 1) индекс исходной вершины, 2) индекс рассматриваемой вершины, вершины отсчета, относительно которой осуществляется поиск; j -1) индекс искомой вершины, 2) столбцовый индекс элемента матрицы смежности; к - 1) номер нижнего, первого, элемента очереди, 2) строковый индекс элемента матрицы смежности; 1 - номер верхнего, последнего, элемента (позиции) стека / очереди. m - счетчик недостижимых вершин; n - количество вершин графа; о - символ, считанный с клавиатуры; р - счетчик найденных вершин; v - результат ввода (переменная принимает два значения: правильный ввод или ошибочный); w, х, у, z - метки.

3) Начало программы. Экран очищается. Вызывается процедура Vvod.

4) Процедура Vvod организует ввод количества вершин n и элементов матрицы смежности а, а также проверку правильности ввода:

а) В цикле. Предлагается ввести n. Цикл работает до тех пор, пока ввод не будет выполнен правильно, при этом выводится сообщение об ошибке.

б) В цикле. Предлагается ввести элементы матрицы а. Если akj принимает значение, отличное от 0 или 1, то формируется сообщение об ошибке и организуется возврат к пункту 4.

в) Проверяется симметричность матрицы: в цикле просматриваются элементы матрицы смежности. Если akj не равно ajk, то выдается сообщение о несимметричности матрицы b, организуется возврат к пункту 4.

5) С помощью цикла организуется «меню» программы (пункты «меню»: поиск в глубину, поиск в ширину, изменение матрицы смежности, вывод из программы). Предлагается выбрать пункт меню, нажав соответствующую клавишу (символ считывается с клавиатуры). Если выбран пункт меню «изменение матрицы», то осуществляется возврат к пункту 4. Если выбран поиск в ширину, то вызываются процедуры Ohistka и VShiriny (переход к пункту 6, а от него к пункту 7). Если выбран поиск в глубину, то вызываются процедуры Ochistka и VGlubiny (переход к пункту 6, а от него к пункту 8). Если выбран выход из программы, то цикл останавливается и программа завершается. Если нажата иная клавиша, то цикл продолжит работу.

6) Процедура Ochistka очищает экран от текста, обнуляет количество недостижимых вершин, очищает «стек / очередь» (заполняет массив с нулями), «обновляет» вершины неорграфа, т.е. делает их непросмотренными (заполняет массив b единицами) и выводит на экран количество вершин n и матрицу смежности а. (Переход к пункту 7 или 8, в зависимости от выбранного варианта поиска).

7) Процедура Vshiriny организует поиск в ширину: вызывается процедура ishodnaja (переход к пункту 9 с последующим возвратом к 7-му). В цикле просматриваются элементы очереди, начиная с первого и заканчивая n-ным. Если элемент очереди пуст ск=0, то цикл завершается, иначе рассматриваемой вершиной i становится вершина, находящаяся в последнем элементе очереди сk; в цикле на основе заполнения матрицы а ищутся новые смежные с i-той j-тые вершины: если аij=1 и bj=l (т.е. i-тая вершина смежна с j-той, и j-тая вершина - новая), то выводится пояснение к поиску и индекс найденной вершины, вершина становится «старой», т.е. уже найденной и помещается в последний элемент очереди, номер 1 которого до этого увеличивается на 1, счетчик р засчитывает найденную вершину. Цикл переходит к просмотру следующего элемента очереди ск. И после просмотра всех элементов выводится сообщение об окончании поиска; при этом если р=1, т.е. найденных вершин, не считая исходной, нет, то выдается сообщение об изолированности исходной вершины. (Переход к пункту 10).

8) Процедура VGlubiny организует поиск в глубину в неорграфе: вызывается процедура ishodnaja (переход к пункту 9 с последующим возвращением к пункту 8). В цикле рассматриваемой вершиной i, становится вершина, находящаяся в последнем элементе стека c, в цикле на основе заполнения матрицы а ищутся новые (непросмотренные) смежные с i-той j-тые вершины: если аij=1 и bj=l (т.е. i-тая вершина смежна с j-той, и j-тая вершина - новая), то на экран выводится пояснение к процессу поиска, вершина «старится» и помещается в последний элемент стека сь номер 1 которого до этого увеличивается на 1, счетчик р засчитывает найденную вершину, осуществляется переход к началу внешнего цикла (из стека извлекается вершина для рассмотрения). Если же не были найдены новые смежные вершины, то внутренний цикл завершается, а во внешнем номер позиции стека уменьшается на 1; выводится сообщение об исчерпанности вершины. Внешний цикл извлекает из стека предыдущую вершину, и процесс поиска новых смежных вершин повторяется до тех пор, пока исходная вершина не исчерпается. Затем выводится сообщение об окончании поиска в глубину, при этом если новых смежных вершин, кроме исходной, не оказалось, то выдается сообщение об изолированности вершины. (Переход к пункту 10).

9) Процедура ishodnaja организует ввод индекса исходной вершины, с которой следует начать поиск, и проверку правильности ввода (в цикле. Предлагается ввести индекс вершины i. Если он не принадлежит промежутку [1; n] или bi=0, т.е. эта вершина была просмотрена (для случая вторичного поиска), то выдается сообщение об ошибке ввода и цикл продолжает работу); выводит пояснение касательно процесса поиска и номер вершины, с которой начинается поиск; «старит» вершину, т.е. делает ее найденной; присваивает номеру последней позиции 1 очереди / стека значение 1; помещает индекс найденной исходной вершины в стек / очередь с; присваивает счетчику найденных вершин р значение 1. (Возврат к пункту 7 или 8, в зависимости от выбранного варианта поиска).

10) После завершения поиска в глубину или ширину вызывается процедура vtorichnaja. Если n не равно р и m не равно р (т.е. общее число вершин и число не достижимых вершин отличаются от количества найденных, то процедура продолжает работу, иначе происходит выход из нее (переход к пункту 5). Процедура vtorichnaja после сравнения обнуляет счетчик недостижимых вершин m; с помощью цикла очищается стек / очередь с (заполняет его нулями), и ищет не просмотренные вершины в массиве b (если находит, то выдает соответствующее сообщение, а счетчик m засчитывает не просмотренную, следовательно, недостижимую вершину). Циклом, если недостижимые вершины найдены (m не равно 0), на экран выводится «подменю». (Пункты «подменю»: вторичный поиск в ширину, вторичный поиск в глубину, выход в основное меню). С клавиатуры считывается символ, соответствующий пункту подменю, и, в зависимости от сделанного выбора, в первом случае вызывается процедура VShiriny (переход к пункту 7, а от него к пункту 10), во втором - процедура VGlubiny (переход к пункту 8, а от него к пункту 10), а в третьем осуществляется выход из процедуры vtorichnaja в основное меню. (Переход к пункту 5). Если была нажата иная клавиша, цикл продолжает работу.

На рисунке 4 представлена структурная схема алгоритма программы.

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

20

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

Рисунок 4 - Структурная схема программы

2.2 Описание диалога с пользователем

Программа начинает свою работу после запуска файла KURSYAK.exe. Когда программа загрузится, на экране ЭВМ появится меню, в котором программа простит задать целое количество вершин, как показано на рисунке 5.

Рисунок 5 - Ввод количества вершин

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

Рисунок 6 - Заполнение матрицы достижимости

После мы с клавиатуры заполняем матрицу достижимости. Когда матрица заполнена, программы выдаёт меню, в котором просит выбрать метод решения поставленной задачи. Где кнопкой S - осущёствляется решение методом поиска в ширину. G - Осуществляет решение методом поиска в глубину. N - Изменение матрицы смежности, а V - выход из программы. Как показано на рисунке 7.

Рисунок 7 - Выбор метода решения

После нажатия кнопки S начинается поиск в ширину. Программа запрашивает, с какой вершины начать поиск. Это показано на рисунке 8.

Рисунок 8 - Запрос начальной вершины, для поиска в ширину

В данном случае мы выбираем вершину 5. После чего программа выдаёт нам результат, который показан на рисунке 9. И снова выводит меню, которое было показано на рисунке 8.

Рисунок 9 - Вывод результата методом поиска в ширину

Дальше мы выбираем метод поиска в глубину и делаем это нажав кнопку G.

После чего программа спрашивает начальную вершину поиска в глубину. Это показано на рисунке 10.

Рисунок 10 - Запрос начальной вершины, для поиска в глубину

В данном случае мы выбираем вершину 3. После чего программа выдаёт нам результат метода поиска в глубину. Как показано на рисунке 11.

Рисунок 11 - Вывод результата методом поиска в глубину

После чего на экране ЭВМ появляется основное меню программы (Рисунок 7 - выбор метода решения). Нажав кнопки N и V программа осуществит: операция по замене матрицы достижимости (Рисунок 6 - заполнение матрицы достижимости.) и выход из программы соответственно.

2.3 Контрольный пример

Дан граф G, изображенный на рисунке 12. Построить остов графа поиском в глубину и поиском в ширину.

Рисунок 12 - Данный граф

1) Поиск в глубину.

Начинаем поиск с любой вершины, допустим, с х1. Выбираем вершину, смежную с х1, например х2. Вершины х1, и х2 соединяем ребром Далее выбираем вершину х3 смежную с х2. Вершины х2 и х3 соединяем ребром. Продолжая двигаться дальше, соединяем вершины х3 и х4. У вершины х4 три смежных вершины - x5, x7 и х8. Дня продолжения поиски можно выбрить любую из них, например x5. Соединяем ребром вершины х5 и x6, а затем x6 и x7. Попав в вершину x7, видим, что смежной с ней является вершина x4. Но продолжай, поиск в данном направлении нельзя, так как вершина x4, не является новой и при соединении вершин x7 и х4 граф уже не будет остовом (будет иметь цикл). Согласно алгоритму возвращаемся в предыдущую вершину, то есть в x6. Так как у x6 нет новых вершин, то но вращаемся в вершину x5. Аналогично из x5 переходим в вершину x4. Вершима x8 является новой (еще не просмотренной смежном вершиной) для х4, поэтому, согласно алгоритму, выбираем вершину х8 и соединяем вершины х4 и х8 ребром, затем соединяем х8 и х9. У х9 нет новых вершин, кроме х1, но соединить эти вершины мы не можем, тан как граф тогда не будет остовом. Мы просмотрели все вершины графа G. Возвращаемся в вершину х1. Найденный остов графа G представлен на рис. 5 а.

2) Поиск в ширину.

Начинаем поиск с любой вершины, например с х1. Соединяем ребрами вершину х1 со всеми смежными ей вершинами - х2, х4 и х9. Теперь по порядку рассматриваем эти смежные вершины. Берем вершину х2. Соединяем ее со всеми смежными ей вершинами, то есть с х3. Следующая по порядку вершины х4. Соединяем ее со всеми смежными вершинами, то есть с x5, x7 и x8. Затем по порядку идет вершина х9, но соединить ее со смежной вершиной х8, мы не можем, так как полученный граф не будет являться остовом. Далее рассматриваем вершины х5, х7, и х8. У х5 есть смежная вершина х6. Соединяем их ребром. У вершин х7 и х8 нет таких смежных вершин. Таким образом, мы получили один из остовов графа G, изображенный на рисунке 13.

Рисунок 13 - Полученный граф

Рассмотренные алгоритмы могут быть использованы для построения всех остовных деревьев графа.

Заключение

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

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

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

Минимальные системные требования: Pentium 2 300 Mhz, 64 Mb RAM, 8 Mb Video Card. Объем 24, 6 кбайт. Операционная система Windows XP Professional Edition (работа программы так же возможна в операционных системах, начиная с MS DOS). Программа написана на языке Паскаль: Turbo Pascal 7.0.

Данная программа реализует алгоритмы поиска в глубину и ширину в неориентированных графах и осуществляет поиск в глубину и ширину в простом неориентированном графе с максимальным количеством вершин 15.

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

1 Белецкая С.Ю. Комбинаторика. Графы. Алгоритмы: Учеб. пособие. - Воронеж: ВГТУ, 2003. -103 с.

2 Емелина Е.И. Основы программирования на языке Паскаль. - М.: финансы и статистика, 1997. -208 с.: ил.

3 Емиличев В.А., Мельников О.И. Лекции по теории графов. - М.: Наука, 1990. -384 с.

4 Епашников А.М., Епашников В.А. Программирование в среде Turbo Pascal 7.0. -3-е изд., стер. - М.: «ДИАЛОГ-МИФИ», 1998. -288 с.

5 Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978. - 213 с.

6 Липский В. Комбинаторика для программистов: пер. с польск. - М.: Мир, 1998. - 213 с.

Приложение А

(обязательное)

Листинг программы

{$I-}

program Kursovaya_rabota;

uses crt;

var i, j, k, l, m, n, p: shortint;

q: char;

a: array [1.. 15,1..15] of shortint;

b, c:array [1..15] of shortint;

s: boolean;

label x;

procedure Vvod;

label w;

begin

w: repeat

writeln ('Vvedite celoe chislo vershin n (ot 1 do 15): ');

readln(n);

s:=IOResult=0;

if (not s) or (n<1) or (n>15)

then write (' Oshibka vvoda! ');

if (not s) or (n<1) or (n>15)

then until (n>0) and (n<16) and s;

writeln ('Vvedite simmetrichnuu matricu smejnosti (0 i 1)');

for k:=1 to n do

begin

for j:=1 to n do

begin

read (a [k, j]);

s:=IOResult=0;

if (not s) or (a [k, j]>1) or (a [k, j]<0)

then begin

write (' Oshibka vvoda! Vvedite celoe chislo vershin n (ot 1 do 15): ');

goto w;

end;

end;

readln;

end;

for k:=1 to n do

for j:=1 to n do

if a [k, j]<>a [j, k]

then begin

write (' Matrica ne simmetrihna! ');

goto w;

end;

end;

procedure Ochistka;

begin

clrscr;

writeln ('Kolichestvo vershin n=', n);

for k:=1 to n do

begin

for j:=1 to n do

write (' ', a [k, j]);

writeln;

b[k]:=1;

c[k]:=0;

end;

m:=0;

end;

procedure ishodnaja;

begin

repeat

writeln ('Vvedite celii nomer vershini, s kotoroi sleduet nachat poisk (ot 1 do n) ');

readln(i);

s:=IOResult=0;

if b[i]=0

then writeln ('Eta vershina uje bila rassmotrena ili ne suwestvuet.');

until (i>0) and (i<16) and (b[i]<>0) and s;

write ('poisk nachinaetca s ishodnoi zadannoi vershini ');

write ('X_', i);

writeln;

b[i]:=0;

l:=1;

p:=1;

c[l]:=i;

end;

procedure VShiriny;

begin

writeln ('…POISK V SHIRINY…');

ishodnaja;

for k:=1 to n do

if c[k]=0

then break

else begin

i:=c[k];

write ('prosmatrivaem vershinu X_', i, ' ');

for j:=1 to n do

if (a [i, j]=1) and (b[j]=1)

then begin

write (' k X_', i, ' prisoedinyaetca ');

write ('X_', j);

writeln;

b[j]:=0;

inc(l);

inc(p);

c[l]:=j;

end;

end;

if p=1

then write ('Eta vershina isolirovanna.');

writeln;

writeln ('… Poisk v shirinu dlya dostijimix vershin okonchen…');

end;

procedure VGlubiny;

label z;

begin

writeln ('…POISK V GLUBINY…');

ishodnaja;

repeat

z: i:=c[l];

for j:=1 to n do

if (a [i, j]=1) and (b[j]=1)

then begin

write (', iz nee spuskaemsya v ');

write ('X_', j);

b[j]:=0;

inc(l);

inc(p);

c[l]:=j;

goto z;

if l>1

then write ('eta vershina ischerpana');

writeln;

end;

dec(l);

until l=0;

if p=1

then write (' eta vershina izolirovana ');

writeln;

writeln ('… Poisk v glubinu dlya dostijimix vershin okonchen…');

end;

procedure vtorichnaja;

label y;

begin

y:if (n<>p) and (m<>p)

then begin

m:=0;

for j:=1 to n do

begin

c[j]:=0;

if b[j]=1

then begin

writeln (' vershina X_', j, ' ne dostijima ');

inc(m);

end;

end;

end

else m:=0;

while m<>0 do

begin

write ('S - poisk v shirinu, G - poisk v glubinu, ');

writeln ('N - izmenenie matrici, V - vixod iz programmi ');

q:=readkey;

case upcase(q) of

'G': begin

Ochistka;

VGlubiny;

goto y;

end;

'S': begin

Ochistka;

VShiriny;

goto y;

end;

'N': Vvod;

'V': halt;

end;

end;

end;

begin

clrscr;

x: Vvod;

repeat

write ('S - poisk v shirinu, G - poisk v glubinu, ');

writeln (' N - izmenenie matrici, V - vixod iz programmi');

repeat

q:=ReadKey;

case upcase(q) of

'N': goto x;

'S': begin

Ochistka;

VShiriny;

end;

'G': begin

Ochistka;

VGlubiny;

end;

'V': halt;

end;

until (upcase(q)='G') or (upcase(q)='S');

vtorichnaja;

until upcase(q)='V';

end.

Размещено на Allbest.ru


Подобные документы

  • Основные понятия теории графов. Матричные способы задания и упорядочение элементов. Применение графов для решения экономической и планово-производственной практики. Постановка, основные определения и алгоритм решения задачи о максимальном потоке.

    курсовая работа [544,2 K], добавлен 22.02.2009

  • Основные понятия, структура и свойства сетей Петри. Рассмотрение принципов анализа двудольных ориентированных графов. Проведение проверки корректности абстрактного сценария. Преимущества использования сетей Петри в моделировании и анализе бизнес систем.

    презентация [98,6 K], добавлен 14.09.2011

  • Понятия и определения теории генетических алгоритмов. Математический базис изобретательской физики. Генетический алгоритм изобретательской задачи. Описание операторов генетических алгоритмов. Система мысленного поиска и слежения в сознании изобретателя.

    курсовая работа [723,2 K], добавлен 22.05.2012

  • Задача выбора оптимальной (с точки зрения минимизации стоимости) прокладки транспортных коммуникаций из исходного пункта во все пункты назначения. Создание модели в терминах теории графов, описание волнового алгоритма, алгоритма Дейкстры, их особенности.

    курсовая работа [214,3 K], добавлен 30.09.2009

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

    курсовая работа [986,8 K], добавлен 31.05.2013

  • Понятие классической транспортной задачи, классификация задач по критерию стоимости и времени. Методы решения задач: симплекс, северо-западного угла (диагональный), наименьшего элемента, потенциалов решения, теория графов. Определение и применение графов.

    курсовая работа [912,1 K], добавлен 22.06.2015

  • Описание проблемы оптимального управления запасами предприятия. Разработка модели оптимальной стратегии заказа новой партии товара. Основные стоимостные характеристики системы для построения модели. Программная реализация, результаты выполнения программы.

    курсовая работа [2,7 M], добавлен 09.09.2017

  • Сущность и понятие сетевого анализа. Виды графов: сетевые, стрелочные, вершинные. Логические взаимосвязи в стрелочном графе. Анализ критического пути с применением графов. Выполнение проекта с минимальными издержками и метод построения прогнозного графа.

    книга [145,4 K], добавлен 09.03.2009

  • Проблема автоматизации расчёта сетевого графика. Вычисление критического пути с помощью ЭВМ. Табличный метод решения проблемы, метод графов. Составление алгоритма, написание программы и решение задачи. графический интерфейс пользователя, ввод данных.

    курсовая работа [39,7 K], добавлен 20.11.2008

  • Формы задачи линейного программирования, каноническая форма. Симплекс-метод: теоретические основы, прямой алгоритм; метод Гомори. Математическая и техническая постановка задачи, программная реализация: запуск, графический интерфейс и созданные функции.

    курсовая работа [578,7 K], добавлен 04.02.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.