Кузьмина Про-228_РГР. Алгоритмы и структуры данных

• Название: Алгоритмы и структуры данных
• Дата: 28.04.2022
• Размер: 458.72 Kb.
• Имя файла: Кузьмина Про-228_РГР.docx
• Тип: Пояснительная записка; #502405

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

Федеральное государственное бюджетное

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

«Уфимский государственный авиационный технический университет»

Факультет информатики и робототехники
Кафедра вычислительной математики и кибернетики

Пояснительная записка к расчетно-графической работе

по дисциплине «Алгоритмы и структуры данных»
Выполнил:

Студент группы ПРО-228 Кузьмина Е.В.

Проверил:

Канд.техн.наук Верхотурова Г.Н.


Уфа – 2021

Y

1Постановка задачи 4

1.1.Определение 4

1.1.Входные данные 5

1.2.Промежуточные данные 5

1.3.Описание алгоритма 5

1.4.Код 6

2Примеры работы программы 9

3Список литературы 10

СОДЕРЖАНИЕ

Y1 Постановка зада

1.1. Определение 3

1.2. Входные данные 4

1.3. Промежуточные данные 4

1.4. Описание алгоритма 4

1.5. Код 5

2 Примеры работы программы 8

3 Список литературы 9

1Постановка задачи 4

1.1.Определение 4

1.1.Входные данные 5

1.2.Промежуточные данные 5

1.3.Описание алгоритма 5

1.4.Код 6

2Примеры работы программы 9

3Список литературы 10

1. Постановка задачи

Написать программу нахождения максимального паросочетания для двудольного графа. Разработать алгоритм решения этой задачи и написать программу.

1. Определение

Определение двудольного графа.

Двудольный граф - граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств.

Определение паросочетания и максимального паросочетания.

Паросочетанием M называется набор попарно несмежных рёбер графа (иными словами, любой вершине графа должно быть инцидентно не более одного ребра из множества M). Мощностью паросочетания назовём количество рёбер в нём.

Наибольшим (или максимальным) паросочетанием назовём паросочетание, мощность которого максимальна среди всех возможных паросочетаний в данном графе.

Описание алгоритма

Алгоритм просматривает все вершины v графа: v = 1 … n. Если текущая вершина v уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем. Иначе — алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.

Поиск увеличивающей цепи осуществляется с помощью специального обхода в глубину.

1. Входные данные

• 
  nodes - вершины в графе
  
• 
  connections – ребра графа
  

1. Промежуточные данные

• 
  checkedNodes – просмотренные вершины
  
• 
  node – просматриваемая на данный момент вершина
  

Выходные данные:

• 
  parArray – найденные паросочетания
  
• 
  lblAnswer – (элемент Label) поле, в которое выводится найденное максимальное паросочетание
  

3. Описание алгоритма

В функции FindMaxPar проверяются вершины на просмотренность. Если вершина еще не просмотрена, она просматривается с помощью обхода в глубину. В функции DFS находится такая вершина, которая связана с этой вершиной и при этом еще не просмотрена в функции выше. Найденная вершина отмечается как просмотренная, в массиве parArray отмечается данное паросочетание.

4. Код

1. 
   using System;
   
2. 
   using System.Collections.Generic;
   
3. 
   using System.ComponentModel;
   
4. 
   using System.Data;
   
5. 
   using System.Drawing;
   
6. 
   using System.Linq;
   
7. 
   using System.Text;
   
8. 
   using System.Threading.Tasks;
   
9. 
   using System.Windows.Forms;
   
10. 
    
    
11. 
    namespace RGRAlg
    
12. 
    {
    
13. 
    public partial class Form1 : Form
    
14. 
    {
    
15. 
    List nodes = new List();
    
16. 
    
    
17. 
    const int MAXNODES = 25;
    
18. 
    int[,] connections = new int[MAXNODES, MAXNODES];
    
19. 
    int[] checkedNodes = new int[MAXNODES];
    
20. 
    int[,] parArray = new int[MAXNODES, MAXNODES];
    
21. 
    
    
22. 
    bool isReadyForCreateNodes = false;
    
23. 
    int numbersOfNode = 0;
    
24. 
    int nodeWidth = 30;
    
25. 
    int nodeHeight = 30;
    
26. 
    
    
27. 
    public Form1()
    
28. 
    {
    
29. 
    InitializeComponent();
    
30. 
    }
    
31. 
    
    
32. 
    private void btnCreateNodes_Click(object sender, EventArgs e)
    
33. 
    {
    
34. 
    isReadyForCreateNodes = true;
    
35. 
    }
    
36. 
    
    
37. 
    private void btnStopCreateNodes_Click(object sender, EventArgs e)
    
38. 
    {
    
39. 
    isReadyForCreateNodes = false;
    
40. 
    }
    
41. 
    
    
42. 
    private void Form1_MouseDown(object sender, MouseEventArgs e)
    
43. 
    {
    
44. 
    if (isReadyForCreateNodes)
    
45. 
    {
    
46. 
    DrawEllipse(e.X, e.Y);
    
47. 
    numbersOfNode++;
    
48. 
    DrawString(numbersOfNode, e.X, e.Y);
    
49. 
    }
    
50. 
    }
    
51. 
    private void DrawEllipse(int x, int y)
    
52. 
    {
    
53. 
    System.Drawing.Pen myPen = new System.Drawing.Pen(System.Drawing.Color.Black);
    
54. 
    System.Drawing.Graphics formGraphics;
    
55. 
    formGraphics = this.CreateGraphics();
    
56. 
    Rectangle ellipse = new Rectangle(x - nodeWidth / 2, y - nodeHeight / 2, nodeWidth, nodeHeight);
    
57. 
    formGraphics.DrawEllipse(myPen, ellipse);
    
58. 
    nodes.Add(ellipse);
    
59. 
    myPen.Dispose();
    
60. 
    formGraphics.Dispose();
    
61. 
    }
    
62. 
    public void DrawString(int numberOfNode, int xNode, int yNode)
    
63. 
    {
    
64. 
    System.Drawing.Graphics formGraphics = this.CreateGraphics();
    
65. 
    string drawString = numberOfNode.ToString();
    
66. 
    System.Drawing.Font drawFont = new System.Drawing.Font("Arial", 14);
    
67. 
    System.Drawing.SolidBrush drawBrush = new System.Drawing.SolidBrush(System.Drawing.Color.Black);
    
68. 
    System.Drawing.StringFormat drawFormat = new System.Drawing.StringFormat();
    
69. 
    formGraphics.DrawString(drawString, drawFont, drawBrush, xNode - nodeWidth / 2, yNode - nodeHeight / 2, drawFormat);
    
70. 
    drawFont.Dispose();
    
71. 
    drawBrush.Dispose();
    
72. 
    formGraphics.Dispose();
    
73. 
    }
    
74. 
    
    
75. 
    private void btnCreateConnect_Click(object sender, EventArgs e)
    
76. 
    {
    
77. 
    DrawConnection(nodes[(int)numFirstNode.Value - 1].X + nodeWidth / 2, nodes[(int)numFirstNode.Value - 1].Y + nodeHeight / 2, nodes[(int)numSecondNode.Value - 1].X + nodeWidth / 2, nodes[(int)numSecondNode.Value - 1].Y + nodeHeight / 2);
    
78. 
    connections[(int)numFirstNode.Value - 1, (int)numSecondNode.Value - 1] = 1;
    
79. 
    connections[(int)numSecondNode.Value - 1, (int)numFirstNode.Value - 1] = 1;
    
80. 
    }
    
81. 
    public void DrawConnection(int x1, int y1, int x2, int y2)
    
82. 
    {
    
83. 
    Pen pen = new Pen(System.Drawing.Color.Black);
    
84. 
    System.Drawing.Graphics formGraphics;
    
85. 
    formGraphics = this.CreateGraphics();
    
86. 
    formGraphics.DrawLine(pen, x1, y1, x2, y2);
    
87. 
    pen.Dispose();
    
88. 
    formGraphics.Dispose();
    
89. 
    }
    
90. 
    
    
91. 
    void FindMaxPar()
    
92. 
    {
    
93. 
    for (int i = 0; i < nodes.Count; i++)
    
94. 
    {
    
95. 
    if(checkedNodes[i] == 1)
    
96. 
    {
    
97. 
    continue;
    
98. 
    }
    
99. 
    else
    
100. 
     {
     
101. 
     checkedNodes[i] = 1;
     
102. 
     DFS(i);
     
103. 
     }
     
104. 
     }
     
105. 
     }
     
106. 
     
     
107. 
     void DFS(int node)
     
108. 
     {
     
109. 
     for (int j = 0; j < nodes.Count; j++)
     
110. 
     {
     
111. 
     if (connections[node, j] == 1 && checkedNodes[j] == 0)
     
112. 
     {
     
113. 
     checkedNodes[j] = 1;
     
114. 
     parArray[node, j] = 1;
     
115. 
     break;
     
116. 
     }
     
117. 
     }
     
118. 
     }
     
119. 
     
     
120. 
     private void btnMaxPar_Click(object sender, EventArgs e)
     
121. 
     {
     
122. 
     lblAnswer.Text = "";
     
123. 
     for (int i = 0; i < nodes.Count; i++)
     
124. 
     {
     
125. 
     for (int j = 0; j < nodes.Count; j++)
     
126. 
     {
     
127. 
     parArray[i, j] = 0;
     
128. 
     }
     
129. 
     checkedNodes[i] = 0;
     
130. 
     }
     
131. 
     
     
132. 
     FindMaxPar();
     
133. 
     
     
134. 
     for (int i = 0; i < nodes.Count; i++)
     
135. 
     {
     
136. 
     for (int j = 0; j < nodes.Count; j++)
     
137. 
     {
     
138. 
     if (parArray[i, j] != 0)
     
139. 
     {
     
140. 
     lblAnswer.Text += (i + 1) + " и " + (j + 1) + " ";
     
141. 
     }
     
142. 
     }
     
143. 
     }
     
144. 
     }
     
145. 
     }
     
146. 
     }
     

Оценка сложности: Алгоритм можно представить, как серию из n запусков обхода в глубину на всём графе. Следовательно, всего этот алгоритм исполняется за время O (n m), что в худшем случае есть O (n^2).

2. Примеры работы программы

3. Список литературы

• 
  Metanit.com — сайт о программировании [Электронный ресурс]. URL: https://metanit.com/sharp/adonet/3.5.php
  
• 
  Stack Overflow — сайт вопросов и ответов для программистов [Электронный ресурс]. URL: https://ru.stackoverflow.com
  
• 
  CyberForum.ru — веб-форум для IT-специалистов [Электронный ресурс]. URL: https://www.cyberforum.ru