СДлб6
.docxМинистерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
ГРАФЫ
Отчет по практической работе №6 по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
Принял:
преподаватель КИБЭВС
Д.Р. Уразаев
Томск 2022
СОДЕРЖАНИЕ
Y
1 Введение 3
Задание 3
2 Ход работы 4
2.1 Ввод графа 4
2.2 Метод Way 5
2.3 Вывод графа 6
2.4 Работа алгоритма 7
Заключение 8
1 Введение
Цель работы: освоить навыки работы с графами и реализовать необходимые методы на языке программирования C#.
Задание
Реализовать возможность работы с графом N узлов, M ребер. Выберете самостоятельно структуру.
Обеспечьте следующие интерфейсные методы:
ввод графа (можно случайным образом)
вывод графа - матрица смежности или весов
2 Ход работы
Ввод графа
С клавиатуры вводятся количество узлов и ребер. Сами элементы задаются случайным образом.
Фрагмент кода представлен на рисунке 1.
Рисунок 2.1 – Ввод графа
Метод Way
В данном методе реализуется алгоритм Дейкстры. Где по условию мы не должны проходить через город C и D.
Фрагмент кода представлен на рисунке 2.
Рисунок 2.2 – Алгоритм Дейкстры
Вывод графа
На рисунке 3 представлен вывод графа.
Рисунок 2.3 – Вывод графа
Работа алгоритма
На рисунке 4 представлена работа алгоритма.
Рисунок 2.4 – Работа алгоритма
Заключение
В процессе выполнения практической работы были освоены навыки работы с графами и, в соответствии с вариантом, реализованы необходимые методы на языке программирования C#.
Приложение А (обязательное)
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;
}
}
}
}
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])
{
possition[j] = possition[indexm] + matrix[indexm, j];
way[j] = way[j] + indexm + ", ";
}
}
}
for (int i = 0; i < Node; i++)
{
way[i] = way[i] + i;
Console.WriteLine($"City number: " + i + " Weight: " + possition[i]);
Console.WriteLine("Way: " + way[i]);
Console.WriteLine();
}
Console.WriteLine();
}
}
}
}