Структура данных типа граф

Содержание

Введение                                                                                                                                                           4

1 Описание поставленной задачи для компьютерной сети                                          5

2 Алгоритмы используемые в задаче                                                                                    6

2.1              Алгоритм обхода графа в глубину                                                                                    6

2.2              Алгоритм нахождения кратчайшего пути                                                                      7

2.3              Алгоритм проверки целостности                                                                                    9

2.4              Алгоритм нахождения точек сочленения                                                                      10

2.5              Алгоритм определения двусвязности                                                                      11

3 Реализация и тестирование программного средства                                           12

Заключение                                                                                                                                             15

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

Приложение А Исходный код программы                                                                      17

Введение

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

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

Все алгоритмы реализованы на языке высокого уровня Python.

1              Описание поставленной задачи для компьютерной сети

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

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

Проверка целостности или связный граф называется, если для всех
x, y ϵ X существует путь из вершины x в вершину y (вершины x и y связанны маршрутом). В программе реализуется алгоритмом поиска в глубину. Алгоритм проверяет все точки, связаны ли они в один единый граф.

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

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

2              Алгоритмы используемые в задаче

2.1              Алгоритм обхода графа в глубину

При обходе в глубину посещается и помечается как посещенная первая

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

После попадания в тупик осуществляется возврат по пройденному пути

пока не будет найдена вершина, у которой есть еще не посещенный сосед, и в

этом направлении таким же образом осуществляется процесс прохождения до

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

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

Рисунок 1. Пример графа.

Начав обход в глубину в вершине 1, посетим последовательно вершины

2, 3, 4, 7, 5 и 6 и достигнем тупика. Затем вернемся в вершину 7 и обнаружим,

что вершина 8 осталась непоселенной. Перейдя в эту вершину, мы оказываемся в тупике и т.д. Возвращаемся назад в исходную вершину, и поскольку все соседние с ней вершины оказались посещенными, обход закончен:

1 нач.  2  3  4  7  5  6 туп.  5  7  8 туп.  7 4  9 туп. 

 4  3  2  1 нач.

В приведенной последовательности посещений вершин маркером отмечены пути возврата. Результирующая последовательность обхода:

1 2 3 4 7 5 6 8 9.

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

DepthTraversal (v)

Visit(v) //посещение вершины

Mark(v) //пометка посещенной вершины

for каждого ребра (v, w) do

if вершина w непомечена then

DepthTraversal(w)

end if

end for

End DepthTraversal

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

2.2              Алгоритм нахождения кратчайшего пути.

Для нахождения кратчайших путей воспользуемся, от одной вершины до всех остальных алгоритмом Беллмана-Форда и методом динамического программирования. Построим матрицу Aij, элементы которой будут обозначать следующее: Aij — это длина кратчайшего пути из s в i, содержащего не более j рёбер.

Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, Ai0 равно 0 при i = s, и  в противном случае.

Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из j − 1 ребра, к которому добавлено последнее ребро. Если про пути длины j − 1 все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.

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

for

  do

for to | V |  − 1

  do for

    if d[v] > d[u] + w(u,v)

      then

return d

Здесь V — множество вершин графа G, E — множество его рёбер, а w — весовая функция, заданная на ребрах графа.

Внешний цикл выполняется |V| - 1 раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.

Вместо массива d можно хранить всю матрицу A, но это требует O(V²) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу Pij.

Если элемент Aij содержит длину кратчайшего пути из s в i, содержащего j рёбер, то Pij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).

Теперь алгоритм Беллмана — Форда выглядит так:

for

  for to | V |  − 1

    do

for to | V |  − 1

  do for

    if Avi > Au,i − 1 + w(u,v)

      then

После выполнения этого алгоритма элементы Ai,j содержат длины кратчайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий. А сам кратчайший путь до вершины i с j ребрами восстанавливается так:

while j > 0

return p

2.3 Алгоритм проверки целостности.

Для проверки целостности графа используем алгоритм обход в глубину. Все существующие вершины в графе присвоим индекс = 0. Алгоритм обхода в глубину изменим добавив в него операцию которая будет присваивать вершине индекс = 1. т.о. все вершины которые будут с индексом 1 и будут связными. А те вершины которые будут с индексом 0 будут не связными с графом.

2.4              Алгоритм нахождение точек сочленения

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

Реализуем рекурсивную функцию void go(int curr, int prev), где curr — текущая вершина, а prev — вершина, из которой мы попали в текущую. При первом вызове curr = r, prev = –1. В теле функции будут выполняться следующие шаги:

1              Запишем в number[curr] номер вершины curr в порядке обхода в глубину.

2              Запишем в L[curr] значение number[curr].

3              Переберем в цикле все вершины, в которые есть ребро из curr. Для каждой такой вершины i выполним следующие действия:

а)              Если вершина i еще не посещена, вызовем рекурсивно функцию go с параметрами i, curr. Если после этого значение L[i] стало меньше, чем L[curr], присвоим L[curr] = L[i].

б)              Если вершина i уже была посещена и ее номер number[i] < number[curr], и при этом i не равно prev (т.е. ребро (i, prev) обратное и возвращается в вершину с меньшим номером), то если L[curr] > number[i], присвоим L[curr] = number[i].

2.5              Алгоритм нахождения двусвязности.

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

Описание алгоритма:

1              Находятся в графе все точки сочленения

2              Удаляются из графа все точки сочленения разбивая граф на несколько частей.

3              Всем вершинам разбитого графа присваиваются индексы = 0

4              Проходим по всем вершинам разбитого графа, если индекс у вершины равен 0, то запускаем процедуру проверки целостности от данной вершины и присваивая вершинам разбитой части графа индекс 1 и затем индекс присваиваемый вершинам повышаем на 1 и при следующем проходе одной из частей разбитого графа, вершинам будет присвоен индекс 2 и т.д. т.

3              Реализация и тестирование программного средства.

Структуры компьютерной сети задается пользователем: количество узловых точек, наличие и пропускная способность каналов передачи данных, добавления и удаления каналов передачи данных и узлов

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

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

Рисунок 2. Интерфейс программы.

Описание меню программы:

1        Прочитать файл.

В этом разделе программа открывает файл 11.txt читает данные

2        Вывод всего графа

Выводиться граф построчно на экран. В каждой строке на первом месте стоит вершина графа и все остальное это смежные с ней вершины и время отклика.

3        Представление графа

Граф выводиться так как он представлен в связной памяти

4        Добавление ребра.

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

5        Добавить новую вершину.

Новая вершина так же создается если такой вершины нет в данном графе.

6        Запись в файл

Записывается граф в файл в том виде, который будет, выведет при выборе меню программы № 2.