Автор работы: Пользователь скрыл имя, 12 Мая 2012 в 15:52, курсовая работа
Часто сталкиваемся с задачами передачи сообщений из узла-источника в узел-адресат и наоборот должны быть организованы маршруты как в прямом, так и в обратном направлениях, причем каждый маршрут может иметь в своем составе транзитные узлы. Поэтому между узлами, находящимися в сигнальном отношении, требуется построить множество маршрутов в каждом направлении. Для того, чтобы рассчитывать такие маршруты необходимо применение методов теории графов. Если узел-источник и узел-адресат изобразить точками (вершинами), а связи – линиями (ребрами), соединяющими соответствующие пары точек, то получиться рисунок, называемый графом.
Целью курсовой работы является разработать программу, решающую задачи над графом. В данной работе описаны алгоритмы определения оптимального маршрута произвольной узловой точки во все остальные, алгоритм проверки целостности (связности) всего графа, алгоритм нахождение точек сочленения, алгоритм двусвязности для определения критических с точек.
Введение 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
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