Структура данных типа граф
Содержание
Введение 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[
3 Переберем в цикле все вершины, в которые есть ребро из curr. Для каждой такой вершины i выполним следующие действия:
а) Если вершина i еще не посещена, вызовем рекурсивно функцию go с параметрами i, curr. Если после этого значение L[i] стало меньше, чем L[curr], присвоим L[curr] = L[i].
б) Если вершина i уже была посещена и ее номер number[i] < number[curr]
2.5 Алгоритм нахождения двусвязности.
Алгоритм двусвязности в данной курсовой работе использует в себе два ране описанные алгоритмы: проверка целостности и нахождение точек сочленения.
Описание алгоритма:
1 Находятся в графе все точки сочленения
2 Удаляются из графа все точки сочленения разбивая граф на несколько частей.
3 Всем вершинам разбитого графа присваиваются индексы = 0
4 Проходим по всем вершинам разбитого графа, если индекс у вершины равен 0, то запускаем процедуру проверки целостности от данной вершины и присваивая вершинам разбитой части графа индекс 1 и затем индекс присваиваемый вершинам повышаем на 1 и при следующем проходе одной из частей разбитого графа, вершинам будет присвоен индекс 2 и т.д. т.
3 Реализация и тестирование программного средства.
Структуры компьютерной сети задается пользователем: количество узловых точек, наличие и пропускная способность каналов передачи данных, добавления и удаления каналов передачи данных и узлов
Программа, решает задачи: определение маршрутов передачи информации из произвольной узловой точки во все остальные, проверка целостности, нахождение точек сочленения, компонент двусвязности для определения критических с точки зрения надежности узлов.
Программа написана на языке высокого уровня Python и реализует консольный интерфейс пользователя. Внешний вид представлен на рисунке 2.
Рисунок 2. Интерфейс программы.
Описание меню программы:
1 Прочитать файл.
В этом разделе программа открывает файл 11.txt читает данные
2 Вывод всего графа
Выводиться граф построчно на экран. В каждой строке на первом месте стоит вершина графа и все остальное это смежные с ней вершины и время отклика.
3 Представление графа
Граф выводиться так как он представлен в связной памяти
4 Добавление ребра.
Добавление ребра от одной вершины к другой происходит если они уже существуют в данном графе. Под временем понимается, время задержки отклика сети.
5 Добавить новую вершину.
Новая вершина так же создается если такой вершины нет в данном графе.
6 Запись в файл
Записывается граф в файл в том виде, который будет, выведет при выборе меню программы № 2.
7 Удалить ребро
Удаляется ребро от одной вершины до другой
8 Удалить вершину
При удалении вершины удаляется как сама вершина так и все ребра связные с ней.
9 Удалить весь граф
Удаляется все вершины
10 Сортировка графа
Сортировка графа происходит в порядке возрастания как по вершинам так и по всем ребрам у каждой вершины.
11 Проверка
Данный раздел проверяется связь по ребру двух вершин
12 Точка сочленения
Программа находит все точки сочленения в графе если таковые имеются и выводит их на экран
13 Проверка целостности
При проверке программа выведет все вершины со значением 1, а если у вершины стоит 0, то такая вершина является не связной с графом
14 Двусвязность
Сначала находятся все точки сочленения и удаляются эти вершины из графа, тем самым граф разбивается на части. Выводиться все вершины и по индексам видно на какие части распался граф.
15 Оптимальный путь
Выводится путь из вершин который является самым быстрым по времени отклика.
Заключение
В ходе курсовой работе были изучены и описаны алгоритмы: определение оптимального маршрута произвольной узловой точки во все остальные, алгоритм проверка целостности (связности) всего графа, алгоритм нахождение точек сочленения, алгоритм двусвязности для определения критических с точек.
Графы это одно из базовых на сегодняшний день методов решения задач и наиболее часто используемых структур данных, в то же время данная структура достаточно проста, чтобы на ее примере можно было изучить общие принципы анализа и реализации структур данных. Реализованное приложение демонстрирует работу алгоритмов графом. Т.о., можно считать, что все задачи выполнены, а цели достигнуты.
Список литературы
1. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. : Пер. с англ. : М. : Издательский дом «Вильямс», 2003. – 384 с. : ил. – Парал. тит. англ.
2. Лекции по дискретной математике: учебное пособие / М. И. Дехтярь – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. – 259 с.: ил., табл.-(Серия «Основы информационных технологий»).
3. Дискретная математика: задачи и решения : учебное пособие / Г.И. Просветов. – М. : БИНОМ. Лаборатория знаний, 2008. – 222с. : ил
4. Дискретная математика. Алгоритмы: Учеб. пособие / Б.Н. Иванов. – М.: Лаборатория Базовых Знаний, 2003. – 288 с.: ил
5. Г. Россум, Ф.Л. Дж.Дрейк, Д.С. Откидач, М. Задка, М. Левис, С. Монтаро, Э.С. Реймонд, А.М. Кучлинг, М.А.Лембург, К.П. Йи, Д.Ксиллаг, Х.Г. Петрилли, Б.А.Варсав, Дж.К. Ахлстром, Дж. Роскинд, Н. Шеменор, С. Мулендер. Язык программирования Python. / 2001 – 454с.
Приложение А
Исходный код программы
# -*- coding: cp1251 -*-
filename = "11.txt"
net_v_grafe = 'net_v_grafe'
a = []
toh_all = []
flag = 1
b = {}
def pvg(u):
global a,b,flag
b[u] = flag
#print u, d
#print b
for k in a:
if k[0][0] == u:
for v in k[1:]:
if b[ v[0] ] == 0:
pvg(v[0])
def r(t1):
global a, b
for i in a:
b[ i[0][0] ] = 0
if t1 == None:
t1 = raw_input("От: ")
pvg(t1)
print b
timer = 0;
tin = {}
fup = {}
bt = {}
def tochka(u, p):
global a, bt, timer, fup, tin, net_v_grafe,toh_all
bt[u] = 1
tin[u] = timer
fup[u] = timer
timer += 1
deti = 0
for k in a:
if k[0][0] == u:
for v in k[1:]:
to = v[0]
if to == p:
continue
if bt[ to ] != 0:
fup[u] = min(fup[u], tin[to])
else:
tochka(to, u)
fup[u] = min(fup[u], fup[to])
if fup[to] >= tin[u] and p != net_v_grafe:
print u # u - точка сочленения
toh_all.append(u)
deti += 1
return toh_all
def t():
global a, bt, timer, net_v_grafe
timer = 0
for i in a:
bt[ i[0][0] ] = 0
uu = tochka('E', net_v_grafe)
return uu
def mnogosvaznost():
global a,flag
temp = a
toh = t()
return toh
dl = {}
p = {}
r = []
def max_put(st):
""" Алгоритм Форда-Беллмана - поиск минимального пути"""
global a,dl
for k in a:
dl[ k[0] ] = 10000000000
dl[st] = 0
p[st] = 'nothing'
i = 1
while i <= len(a):
for k in a:
u = k[0]
for r in k[1:]:
if dl[u] > dl[ r[0] ] + int(r[1]):
dl[u] = dl[ r[0] ] + int(r[1])
p[u] = r[0]
i+=1
def pr(g):
global p, r
if g != 'nothing':
r = [ g ] + r
pr( p[g] )
def mp():
global dl, r, p
s = raw_input("От: ")
f = raw_input("До: ")
max_put(s)
print dl[f]
pr(f)
print r
print dl
def vivod(t):
for dannie in t:
sep = ','
kod = sep.join(dannie)
print kod
return
def vershiny():
"""Собирает все вершины в один список"""
global a
i = 0
n = []
while i < len(a):
el_a = a[i]
n.append(el_a[0])
i+=1
return n
def read_graph():
"""Процедура открывает файл и считывает граф представленный списком смежности"""
global filename,a
infile = open(filename, 'r')
a = []
for line in infile:
words = line.split()
a.append([words[0]])
b = []
for w in words[1:]:
b.append(w)
if len(b) == 2:
a[-1].append(b)
b = []
infile.close()
return a
def graf_postr():
"""Построитель графа. Записывает в строчку вершину и все связи"""
global a
for elem_a in a:
print elem_a
return a
def nev_uzel():
global a
b = []
prov = False
t1 = raw_input("Новый узел: ")
for el_a in a:
if el_a[0] <> t1:
prov = True
if prov:
b.append(t1)
a.append(b)
else:
print 'Error Такого узла нет!'
return a
def nev_rebro():
"""Добавляет новое ребро"""
global a
b = []
c = []
t1 = raw_input("От: ")
t2 = raw_input("До: ")
t3 = raw_input("Время: ")
if a == []:
b.append(t1)
c.append(t2)
c.append(t3)
b.append(c)
a.append(b)
b,c=[],[]
b.append(t2)
c.append(t1)
c.append(t3)
b.append(c)
a.append(b)
b,c=[],[]
elif a <> []:
ver = vershiny()
n = True
for el_a in a:
for el in el_a:
if el_a[0] == t1 and el[0] == t2:
n = False
else:
pass
if n:
i = 0
while i < len(a):
elem_1 = a[i]
if t1 in elem_1 and t2 not in ver:
c.append(t2)
c.append(t3)
elem_1.append(c)
c = []
b.append(t2)
c.append(t1)
c.append(t3)
b.append(c)
a.append(b)
b,c=[],[]
elif t1 in elem_1 and t2 in ver:
c.append(t2)
c.append(t3)
elem_1.append(c)
c = []
elif t2 in elem_1 and t2 in ver:
c.append(t1)
c.append(t3)
elem_1.append(c)
c = []
i +=1
else:
print "ERROR, Такого ребра нет"
#graf_postr()
return a
def zapis_file():
"""Запись графа в файл"""
global filename,a
file=open(filename,'w')
for el_a in a:
file.write(str(el_a[0]))
file.write(' ')
i = 1
while i < len(el_a):
el = el_a[i]
file.write(str(el[0]))
file.write(' ')
file.write(str(el[1]))
file.write(' ')
i += 1
file.write('\n')
file.close()
return a
def del_uzel(t1,graf):
"""Удаляет Вершину"""
prov = False
if t1 == None:
t1 = raw_input("Узел: ")
for el_a in graf:
if el_a[0] == t1:
prov = True
if prov:
for el_a in graf:
if t1 == el_a[0]:
graf.remove(el_a)
for el_a in graf:
for el in el_a:
if t1 == el[0]:
el_a.remove(el)
else:
print 'Net takogo Uzla'
return graf
def dvusvaznost():
global a,flag,b
temp = a[:]
toh = t()
for el_toh in toh:
del_uzel(el_toh,temp)
for i in temp:
b[ i[0][0] ] = 0
for u in temp:
if b[u[0]] == 0:
pvg(u[0])
flag += 1
print b
return b
def del_rebro():
"""Удаляет Ребро"""
x = raw_input("От: ")
y = raw_input("До: ")
def uzel(u,m):
global a
for el_a in a:
if el_a[0] == u:
j = 1
while j < len(el_a):
el = el_a[j]
if el[0] == m:
el_a.remove(el_a[j])
j+=1
return a
prov = False
for el_a in a:
for el in el_a:
if el_a[0] == x and el[0] == y:
prov = True
if prov:
uzel(x,y)
uzel(y,x)
else:
print 'Нет такого ребра'
return a
def del_graf():
global a
i = 0
while i < len(a):
del a[i]
return b
def del_all():
"""Удаляет весь граф"""
global a
a = []
return a
def a_sort():
"""Сортирует граф по убыванию. Сначала сортирует по вершинам,
затем сортирует в нутри вершины связные вершины"""
global a
j = 0
while j < len(a):
i = 1
while i < len(a):
el_1_a = a[i]
el_0_a = a[i-1]
if el_1_a[0] < el_0_a[0]:
a[i],a[i-1] = a[i-1],a[i]
i+=1
j+=1
for el_a in a:
if len(el_a)> 2:
j = 1
while j < len(el_a):
i = 2
while i < len(el_a):
el_1_a = el_a[i]
el_0_a = el_a[i-1]
if el_1_a[0] < el_0_a[0]:
el_a[i],el_a[i-1] = el_a[i-1],el_a[i]
i+=1
j+=1
return a
def vopros():
"""При выхода из меню задает вопрос, записывать или нет в файл граф"""
print 'Записать граф в файл? (1/0/Отмена)'
t = raw_input('Введите номер меню -> ')
if t == '1':
zapis_file()
loop = False
print 'Goodbye'
elif t == '0':
loop = False
print 'Goodbye'
else:
loop = True
return loop
def proverka():
global a
t1 = raw_input("От: ")
t2 = raw_input("До: ")
n = 0
for el_a in a:
for el in el_a:
if el_a[0] == t1 and el[0] == t2:
n +=1
else:
pass
if n > 0:
print 'Да'
else:
print 'Нет'
return a
def Menu():
"""Меню программы"""
global a
verchina = None
loop = True
while loop == True:
print '=============================
print ' ГРАФ'
print '=============================
print ' 1 – Прочитать файл'
print ' 2 – Вывод всего графа'
print ' 3 – Построение графа'
print ' 4 – Новое ребро'
print ' 5 – Новый узел'
print ' 6 – Записать в файл'
print ' 7 - Удалить ребро'
print ' 8 – удалить узел'
print ' 9 – Удалить весь граф'
print ' 10 – Сортировка графа'
print ' 11 – Проверка ближайшей вершины'
print ' 12 – Точка сочленения'
print ' 13 – Проверка целостности'
print ' 14 - Двусвязность'
print ' 15 – Оптимальный путь'
print ' 0 - Выход'
print '=============================
response = raw_input(' Введите номер меню -> ')
if response == '1':
read_graph()
elif response == '2':
graf_postr()
elif response == '3':
print a
elif response == '4':
nev_rebro()
elif response == '5':
nev_uzel()
elif response == '6':
zapis_file()
elif response == '7':
del_rebro()
elif response == '8':
del_uzel(verchina,a)
elif response == '9':
del_all()
elif response == '10':
a_sort()
elif response == '11':
proverka()
elif response == '12':
t()
elif response == '13':
r(verchina)
elif response == '14':
dvusvaznost()
elif response == '15':
mp()
elif response == '0':
loop = vopros()
else:
print 'Unrecognized command. Try again.'
return response
print Menu()
3