Представление ориентированных графов
Оглавление
Задание для курсовой работы.. 3
Введение. 4
1 Теоретические основы теории графов. 5
1.1 Основы понятия граф. 5
1.2 Представление ориентированных графов. 6
1.3 Поиск самого длинного цикла. 7
1.4 Обход графа в ширину. 7
1.5 Определить кратчайший путь из заданной вершины в остальные. 8
1.6 Построение минимального остовного дерева алгоритмом Крускала. 8
2 Разработка программы, реализующей алгоритмы на графах. 9
2.1 Исходные данные. 9
2.2 Структура данных. 9
2.3 Результаты работы программы.. 9
Заключение. 13
Литература. 14
Задание для курсовой работы
1. Написать программу на языке Паскаль, реализующую алгоритмы на графах. А именно: определить самый длинный цикл в графе, выполнить обход графа в ширину, определить кратчайший путь из заданной вершины во все остальные, построить минимальное остовное дерево с помощью алгоритма Крускала.
2. Входной информацией для программы будет ориентированный связный граф с числом вершин не более шести, каждое ребро которого имеет определенный неотрицательный вес. Выбрать способ ввода входной информации.
3. Входная и выходная информация для каждого отдельного пункта задания должна быть определена из содержания задания.
4. Оформить пояснительную записку по курсовой работе.
Введение
Решение любой вычислительной задачи предполагает выполнение определенной последовательности шагов. При этом один и тот же результат может быть получен различными способами. Один из способов может быть более эффективным, другой менее эффективным, но более легким в реализации. Алгоритм, будучи той самой последовательностью шагов, можно оценить, как это будет показано дальше. Имея набор алгоритмов, предназначенных для решения какой-либо проблемы, программист в состоянии выбирать удовлетворяющий его нуждам.
|
|
|
Теория графов является одним из самых важных разделов дискретной математики. Графы и алгоритмы на графах имеют большое практическое применение в прикладных областях науки. Родоначальником теории графов считается Леонард Эйлер.
Теория графов используется в химии для описания структур, путей сложных реакций, она позволяет точно определить число теоретически возможных изомеров углеводородов и других органических соединений. Теория графов широко применяется в коммуникационных и транспортных системах, в частности, для маршрутизации данных в Интернете. Множество практических применений теории этот раздел имеет в экономике и логистике, а также в схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).
|
|
|
Целью курсовой работы является реализация графов и операций над ними.
Задачи:
- изучить основные понятия теории графов;
- изучить алгоритмы на графах (обход в глубину и ширину, поиск кратчайшего пути между вершинами и т.п.);
- написать программу, реализующую некоторые алгоритмы на графах;
- провести тестирование программы.
Теоретические основы теории графов
Основы понятия граф
Во многих задачах, встречающихся в компьютерных науках, математике, технических дисциплинах часто возникает необходимость наглядного представления отношений между какими-либо объектами. Ориентированные и неориентированные графы – естественная модель для таких отношений.
Граф - совокупность непустого множества вершин и наборов пар вершин (связей между вершинами); основной объект изучения математической теории графов.
Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Граф, или неориентированный граф G - это упорядоченная пара G := (V, E), где V - это непустое множество вершин или узлов, а E - множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами. V и E обычно считаются конечными множествами.
|
|
|
Ориентированный граф (или сокращенно орграф) G = (V, Е) состоит из множества вершин V и множества дуг Е. Вершины также называют узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, a w – концом дуги. Дугу (v, w) часто записывают как v → w.
Путем в орграфе называется последовательность вершин v1, v2, …, vn для которой существуют дуги v1 → v2, v2 → v3, …, vn – 1 → vn. Этот путь начинается в вершине v1 и, проходя через вершины v2, v3, …, vn – 1, заканчивается в вершине vn. Длина пути – это количество дуг, составляющих путь, в данном случае длина пути равна n – 1.
Путь называется простым, если все вершины на нем, за исключением, может быть, первой и последней, различны. Цикл – это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.
Во многих приложениях удобно к вершинам и дугам орграфа присоединить какую-либо информацию. Для этих целей используется помеченный орграф, т. е. орграф, у которого каждая дуга и/или каждая вершина имеет соответствующие метки. Меткой может быть имя, вес или стоимость (дуги), или значение данных какого-либо заданного типа.
|
|
|
На рис. 1.1 показан помеченный орграф, в котором каждая дуга имеет буквенную метку. Этот орграф имеет интересное свойство: любой цикл, начинающийся в вершине 1, порождает последовательность букв а и b, в которой всегда четное количество букв а и b.
a
| 1 |
| 2 |
| a |
| b |
| b |
| a |
| 4 |
| 3 |
a
Рис. 1.1. - Помеченный орграф
В помеченном орграфе вершина может иметь как имя, так и метку. Часто метки вершин используются в качестве имен вершин. Так, на рис. 1.1 числа, помещенные в вершины, можно интерпретировать как имена вершин и как метки вершин.
Представление ориентированных графов
Для представления ориентированных графов можно использовать раз-личные структуры данных. Выбор структуры данных зависит от операторов, которые будут применяться к вершинам и дугам орграфа. Одним из наиболее общих представлений орграфа G = (V, Е) является матрица смежности.
Предположим, что множество вершин V = {1, 2, …, n}. Матрица смежности для орграфа G – это матрица А размера n x n со значениями булевого типа, где A[i, j] = true тогда и только тогда, когда существует дуга из вершины i в вершину j. Часто в матрицах смежности значение true заменяется на 1, а значение false – на 0. Время доступа к элементам матрицы смежности зависит от размеров множества вершин и множества дуг. Представление орграфа в виде матрицы смежности удобно применять в тех алгоритмах, в которых надо час- то проверять существование данной дуги.
Обобщением описанного представления орграфа с помощью матрицы смежности можно считать представление помеченного орграфа также по- средством матрицы смежности, но у которой элемент A[i, j] равен метке дуги i → j. Если дуги от вершины i к вершине j не существует, то значение A[i, j] не может быть значением какой-либо допустимой метки, а может рассматриваться как «пустая» ячейка.
На рис. 1.2 показана матрица смежности для помеченного орграфа, приведенного на рис. 1.1. Здесь дуги представлены меткой символьного типа, а пробел используется при отсутствии дуг.
Основной недостаток матриц смежности заключается в том, что она требует O(n2) объема памяти, даже если дуг значительно меньше, чем n2. Поэтому для чтения матрицы или нахождения в ней необходимого элемента требуется время порядка O(n2), что не позволяет создавать алгоритмы с временем O(n) для работы с орграфами, имеющими порядка O(n) дуг.
| а b b а b a |
| b |
| а |
1
2
3
4
Рис. 1.2. - Матрица смежности для помеченного орграфа из рис. 1.1
Поиск самого длинного цикла
Циклами графа называют замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин. Циклы можно описать набором рёбер.
Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину находит ребро, которое приводит к уже посещённой вершине (обратная дуга). Таким же образом, все обратные рёбра, которые алгоритм поиска в глубину обнаруживает, являются частями циклов. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n−1 рёбер могут быть рёбрами дерева.
Обход графа в ширину
Поиск в ширину – другой метод систематического обхода вершин графа. Он получил свое название из-за того, что при достижении во время обхода любой вершины v далее рассматриваются все вершины, смежные с вершиной v, т. е. осуществляется просмотр вершин «в ширину».
Так же, как и при применении поиска вглубь, посредством метода поиска в ширину при обходе графа создается остовный лес. Если после достижения вершины х при рассмотрении ребра (х, у) вершина у не посещалась ранее, то это ребро считается ребром дерева. Если же вершина у уже посещалась ранее, то ребро (х, у) будет поперечным ребром, так как оно соединяет вершины, не связанные наследованием друг друга.
При выполнении алгоритма поиска в ширину, ребра дерева помещаются в первоначально пустой массив Т, формирующий остовный лес. Посещенные вершины графа заносятся в очередь Q. Массив mark (метка) отслеживает состояние вершин: если вершина v пройдена, то элемент mark[v] принимает значение visited (посещалась), первоначально все элементы этого массива имеют значение unvisited (не посещалась). Отметим, что в этом алгоритме во избежание повторного помещения вершины в очередь пройденная вершина помечается как visited до помещения ее в очередь. Процедура поиска в ширину работает на одной связной компоненте. Если граф не односвязный, то эта процедура должна вызываться для вершин каждой связной компоненты.
Дата добавления: 2021-03-18; просмотров: 217; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!