СДлб6
.pdf
Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
ГРАФЫ
Отчет по практической работе №6 по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
Принял:
преподаватель КИБЭВС
Д.Р. Уразаев
Томск 2022
СОДЕРЖАНИЕ
1 Введение....................................................................................................................................... |
3 |
|
Задание |
............................................................................................................................................ |
3 |
2 Ход работы ................................................................................................................................... |
4 |
|
2.1 |
Ввод графа ......................................................................................................................... |
4 |
2.2 |
Метод Way......................................................................................................................... |
5 |
2.3 |
Вывод графа ...................................................................................................................... |
6 |
2.4 |
Работа алгоритма............................................................................................................... |
7 |
Заключение ..................................................................................................................................... |
8 |
|
2
1 Введение
Цель работы: освоить навыки работы с графами и реализовать необходимые методы на языке программирования C#.
Задание
Реализовать возможность работы с графом N узлов, M ребер. Выберете самостоятельно структуру.
Обеспечьте следующие интерфейсные методы:
ввод графа (можно случайным образом)
вывод графа - матрица смежности или весов
3
2 Ход работы
2.1Ввод графа
Склавиатуры вводятся количество узлов и ребер. Сами элементы задаются случайным образом.
Фрагмент кода представлен на рисунке 1.
Рисунок 2.1 – Ввод графа
4
2.2Метод Way
Вданном методе реализуется алгоритм Дейкстры. Где по условию мы не должны проходить через город C и D.
Фрагмент кода представлен на рисунке 2.
Рисунок 2.2 – Алгоритм Дейкстры
5
2.3 Вывод графа
На рисунке 3 представлен вывод графа.
Рисунок 2.3 – Вывод графа
6
2.4 Работа алгоритма
На рисунке 4 представлена работа алгоритма.
Рисунок 2.4 – Работа алгоритма
7
Заключение
В процессе выполнения практической работы были освоены навыки работы с графами и, в соответствии с вариантом, реализованы необходимые методы на языке программирования C#.
8
Приложение А
(обязательное)
using System;
namespace sdlab6
{
class program
{
static void Main(string[] args)
{
Console.Write("Enter count nodes:");
int nodes = Convert.ToInt32(Console.ReadLine()); Console.Write("\nEnter number edges:");
int edges = Convert.ToInt32(Console.ReadLine()); Console.Write("Enter number City А: ");
int CityA = Convert.ToInt32(Console.ReadLine()); Console.Write("Enter number City C: ");
int CityC = Convert.ToInt32(Console.ReadLine()); Console.Write("Enter number City D: ");
int CityD = Convert.ToInt32(Console.ReadLine()); Graph graph = new Graph(nodes, edges); graph.Conclusion();
graph.Way(CityA, CityC, CityD);
Console.ReadLine();
}
class Graph
{
int Node, Edge; int[,] matrix; public Graph(int nodes, int edges)
{
this.Node = nodes; this.Edge = edges;
matrix = Matrix(this.Node, this.Edge);
}
private static int[,] Matrix(int Node, int Edge)
{
Random rand = new Random();
int[,] matrix = new int[Node, Node]; int count = 0;
for (int i = 0; i < Node; i++)
{
for (int j = i; j < Node; j++)
{
if (i == j)
{
matrix[i, j] = 0;
}
else
{
if (count < Edge)
{
matrix[i, j] = matrix[j, i] = rand.Next(0, 20); if (matrix[i, j] != 0)
count++;
}
else
{
matrix[i, j] = matrix[j, i] = 0;
}
} |
9 |
}
}
if (count < Edge)
{
for (int i = 0; i < Node; i++)
{
for (int j = i; j < Node; j++)
{
if (count < Edge && matrix[i, j] == 0 && i != j)
{
matrix[i, j] = matrix[j, i] = rand.Next(1, 20); count++;
}
}
}
}
return matrix;
}
public void Conclusion()
{
Console.WriteLine("\nMatrix\n"); for (int i = 0; i < Node; i++)
{
for (int j = 0; j < Node; j++)
{
Console.Write(matrix[i, j] + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
public void Way(int City, int AnotherCity, int AnotherCity2)
{
int[] possition = new int[Node]; string[] way = new string[Node]; bool[] node = new bool[Node]; int min;
int indexm = 0;
for (int i = 0; i < Node; i++)
{
possition[i] = 10000; node[i] = false; way[i] = "";
}
possition[City] = 0; possition[AnotherCity] = 0; possition[AnotherCity2] = 0;
node[AnotherCity] = true;
for (int i = 0; i < Node - 1; i++)
{
min = 10000;
for (int j = 0; j < Node; j++)
{
if (!node[j] && possition[j] < min)
{
min = possition[j]; indexm = j;
}
}
node[indexm] = true;
for (int j = 0; j < Node; j++)
{
if (!node[j] && matrix[indexm, j] > 0 && possition[indexm] != 10000 && possition[indexm] + matrix[indexm, j] < possition[j])
10