Jizzax filiali amaliy matematika fakulteti «kompyuter ilmlari va dasturlashtirish»

Kruskal algoritmi quyidagi afzalliklarga ega: 

Bu algoritm o'zining ishga tushgan ishni sodda, ishonchli va samarali 
ko'rish uchun kam miqdorli tirishlar ishlatadi. 

Algoritm o'zining so'rovnoma bo'sh joylaridan foydalanadi. 

Algoritmning samarasi katta graflar uchun, bir necha ming tomonlar 
uchun yoki doimiy saqlash uchun zarur bo'lgan boshqa algoritmlarga 
nisbatan yuqori. 

Algoritm grafdagi eng qisqa tomonlarni topishni ta'minlaydi. 

Algoritm grafdagi hamma tomonlarni bog'lashni ta'minlaydi. 
Kruskal algoritmining kamchiliklari quyidagilardir: 

Algoritmning ishlab chiquvchi narsalar vaqt va xotin sarflashi talab 
qiladi. 

Algoritmning ishlab chiquvchi narsalar mamlakatdan mamlakatga 
harakat qilishni ta'minlashi kerak. 
Kruskal algoritmi dasturi C# tilida yozilishi 
Quyidagi C# kodi Kruskal algoritmini amalga oshirish uchun 
yozilgan. Bu dastur, Windows Forms-ida ishlaydi va foydalanuvchi bitta 
grafni kiritadi. Dastur, Kruskal algoritmi orqali barcha tugallanadigan 
tomonlarni bog'lash uchun kam miqdorli tirishlar ishlatadi. 
using System; 
using System.Collections.Generic; 
using System.ComponentModel; 
using System.Data; 
using System.Drawing; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
using System.Windows.Forms; 
 

---

namespace Kruskal_Algorithm 
{ 
public partial class Form1 : Form 
{ 
private int vertices = 0; 
private int[,] graph; 
public Form1() 
{ 
InitializeComponent(); 
} 
 
private void btnDraw_Click(object sender, EventArgs e) 
{ 
vertices = Convert.ToInt32(txtVertices.Text); 
graph = new int[vertices, vertices]; 
 
for (int i = 0; i < vertices; i++) 
{ 
for (int j = 0; j < vertices; j++) 
{ 
if (i == j) 
{ 
graph[i, j] = 0; 
} 
else 
{ 
graph[i, j] = -1; 
} 
} 
} 
 
int edgeCount = Convert.ToInt32(txtEdges.Text); 
 
for (int i = 0; i < edge ; i < edgeCount; i++) 
{ 
int fromVertex = Convert.ToInt32(txtFromVertex.Text); 
int toVertex = Convert.ToInt32(txtToVertex.Text); 
int weight = Convert.ToInt32(txtWeight.Text); 
graph[fromVertex, toVertex] = weight; 
graph[toVertex, fromVertex] = weight; 
} 

---

 
DrawGraph(); 
} 
 
private void DrawGraph() 
{ 
Bitmap bitmap = new Bitmap(picGraph.Width, picGraph.Height); 
Graphics graphics = Graphics.FromImage(bitmap); 
 
int radius = 100; 
Point center = new Point(picGraph.Width / 2, picGraph.Height / 2); 
double angle = 2 * Math.PI / vertices; 
 
List
 verticesPositions = new List
(); 
 
for (int i = 0; i < vertices; i++) 
{ 
int x = Convert.ToInt32(center.X + radius * Math.Cos(i * angle)); 
int y = Convert.ToInt32(center.Y + radius * Math.Sin(i * angle)); 
 
Point vertexPosition = new Point(x, y); 
verticesPositions.Add(vertexPosition); 
 
graphics.FillEllipse(Brushes.White, x - 20, y - 20, 40, 40); 
graphics.DrawEllipse(Pens.Black, x - 20, y - 20, 40, 40); 
graphics.DrawString(i.ToString(), new Font("Arial", 12), 
Brushes.Black, x, y); 
} 
 
List> edges = new List>(); 
 
for (int i = 0; i < vertices; i++) 
{ 
for (int j = i + 1; j < vertices; j++) 
{ 
if (graph[i, j] != -1) 
{ 
edges.Add(new Tuple(i, j)); 
} 
} 
} 

---

 
edges = edges.OrderBy(edge => graph[edge.Item1, 
edge.Item2]).ToList(); 
 
foreach (var edge in edges) 
{ 
Point from = verticesPositions[edge.Item1]; 
Point to = verticesPositions[edge.Item2]; 
 
graphics.DrawLine(Pens.Black, from, to); 
} 
 
picGraph.Image = bitmap; 
} 
}