6 практика
.pdfМинистерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра комплексной информационной безопасности электронно-
вычислительных систем (КИБЭВС)
Графы Отчет по практической работе №6
по дисциплине «Структуры данных»
Студент гр. 711-2
_______ Е. П. Толстолес
_______
Принял:
преподаватель КИБЭВС
_______ Н.С. Репьюк
_______
Томск 2022
СОДЕРЖАНИЕ:
1Введение……………………………………………………………...………….3
2Ход работы………………………………………………………………………4
2.1Инициализация графа и заполнение его весами……...………………...4
2.2Выбор пунктов для нахождения кратчайшего пути……………………4
3Заключение…………………………………………………………………..…..5
Приложение А…………………………………………………………………..…6
2
1 Введение
Целью работы является реализовать возможность работы с графом N
узлов, M ребер. Выберете самостоятельно структуру. Обеспечьте следующие интерфейсные методы:
ввод графа (можно случайным образом, можно вводить с клавиатуры)
НЕДОПУСТИМО работать только с конечным числом ребер и узлов.
Приложение должно позволять вводить разные графы.
вывод графа - матрица смежности или весов.
в заданной системе дорог для каждой пары городов указать длину кратчайшего пути между ними, а также восстановить путь.
3
2Ход работы
2.1Инициализация графа и заполнение его весами
На рисунке 2.1 представлена инициализация графа и заполнения его случайными элементами из массива mas.
Рисунок 2.1 – Инициализация графа и его заполнение
2.2 Выбор пунктов для нахождения кратчайшего пути
На рисунке 2.2 представлен выбор пунктов для поиска кратчайшего пути и вывод кратчайшего пути через смежную матрицу.
Рисунок 2.2 – Вывод кратчайшего пути от А до В
4
3Заключение
Входе выполнения практической работы была разработана программа для работы с графами. Разработан дружественный интерфейс и реализованы все необходимые методы нахождения кратчайшего пути в графе.
Наиболее затруднительным было создание и инициализация графа.
Отчет был составлен согласно ОС ТУСУР 2021.
5
Приложение А
(обязательное)
Программа для работы с графами и поиска кратчайшего пути
import random
print("Введите количество узлов") N = int(input())
a = ((N ** 2) - N) // 2
print("Введите число рёбер от", N - 1, "до", a) M = int(input())
count = 0 mas = []
for l in range(0, 100000): # Создание списка с расстоянием дорог count += 1
x1 = random.randint(1, 100) mas.append(x1)
if count == M: break
a = [[0] * N for i in range(N)] # Создание матрицы дорог и заполнение главной диагонали
for i in range(N):
for j in range(N): if i == j:
a[i][j] = 0 else:
a[i][j] = -1
l = 0
for x in range(N): # Заполнение матрицы длинной дорог for y in range(N):
for v in range(10 ** 100):
irand = (random.randint(1, 1000000)) % N jrand = (random.randint(1, 1000000)) % N if a[irand][jrand] == -1:
a[irand][jrand] = mas[l] a[jrand][irand] = mas[l] l += 1
if l == M: break
else: continue
break break
for row in a:
print(' '.join([str(elem) for elem in row]))
print("Введите пункт отправки") A = int(input())
print("Введите пункт назначения") B = int(input())
for k in range(0, N, 1):
for d in range(0, N, 1):
for g in range(0, N, 1):
if a[d][g] > a[d][k] + a[k][g]: a[d][g] = a[d][k] + a[k][g]
6
print("Кратчайший путь из пунка А в пункт В") print(a[A - 1][B - 1])
7