Графы

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра комплексной информационной безопасности электронно-вычислительных систем (КИБЭВС)

ГРАФЫ

Отчет по практической работе №6                                                                              по дисциплине «Структуры данных»

Студент гр. :

________

__.__.2021

Руководитель  

Доцент каф. КИБЭВС  

_________

__.__.2021

Томск 2021

Содержание

Введение        3

Основная часть        4

Заключение        6

Приложение        7

1 Введение

Цель работы: получить навыки и освоить способы представления графов. Реализовать различные алгоритмы для работы с графом. Для написания программ в данной практической работе будет использоваться язык программирования C#.

В практической работе выполняется задание варианта №7.

Реализовать возможность работы с графом N узлов, M ребер. Выберете самостоятельно структуру. Обеспечьте следующие интерфейсные методы:

• ввод графа (можно случайным образом);
• вывод графа - матрица смежности или весов.

Задана система дорог. Найти такой город, для которого сумма расстояний до остальных городов максимальна.

2 Основная часть

С помощью языка программирования C# была реализована неориентированная матрица смежности для вывода графа и дальнейшей работы с ним (см. Приложение А).

На рисунке 1 представлен код функции CreateMatrix() которая реализовывает ввод графа. Создается двумерный массив и с помощью цикла for рандомно происходит его заполнение. В строке кода 16 происходит заполнение главной диагонали нулями, относительно этой диагонали элементы матрицы будут симметричны. В строке кода 20 реализуется обратной порядок для симметрии матрицы.

[pic 1]

Рисунок 1 – Функция CreateMatrix()

На рисунке 2 представлен код функции PrintMatrix() которая реализовывает вывод графа. На вход функции подается уже заполненная числами матрица и размерность массива.

[pic 2]

Рисунок 2 – Функция PrintMatrix()

На рисунке 3 представлен код функции CountDist() которая находит город, для которого сумма расстояний до остальных городов максимальна. Создаются 2 переменные chislo и gorod которые впоследствии используются для вывода информации о сумме расстояний и городе на экран. В строках кода 42–45 находится сумма всех элементов в строке матрицы.

[pic 3]

Рисунок 3 – Функция CountDist()

На рисунке 4 представлен код функции Floid() которая реализовывает алгоритм Флойда для нахождения длины кратчайших путей.

[pic 4]

Рисунок 4 – Функция Floid()

Пример работы программы изображен на рисунке 5.

[pic 5]

Рисунок 5 – Работа программы

3 Заключение

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