Нехай задано зважений неорієнтований зв'язний граф з N вершинами та M ребрами.
Остовне дерево (каркас) - підграф графа, який:
1) містить усі вершини графа,
2) є деревом (не містить циклів).
Компонента зв'язності - зв'язний підграф, до якого неможливо додати жодну вершину без втрати зв'язності.
1. Видалити всі ребра з графа
2. Відсортувати ребра за зростанням ваги
3. Послідовно додавати ребра, перевіряючи, чи не утворюють вони циклу
4. Якщо ребро утворює цикл - не додавати його
Ребро (Vi,Vj) позначимо Xi,j
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
namespace GraphVisualization
{
// Структура для представлення ребра графа
struct Edge
{
public MyPoint Point1; // Перша точка ребра
public MyPoint Point2; // Друга точка ребра
public int Weight; // Вага ребра (довжина)
// Конструктор ребра
public Edge(MyPoint point1, MyPoint point2, int weight)
{
Point1 = point1;
Point2 = point2;
Weight = weight;
}
}
// Структура для представлення точки графа
struct MyPoint
{
public int Id; // Ідентифікатор точки
public int X; // Координата X
public int Y; // Координата Y
// Конструктор точки
public MyPoint(int id, int x, int y)
{
Id = id;
X = x;
Y = y;
}
}
// Головна форма програми
public partial class Form1 : Form
{
private Bitmap bitmap; // Бітова карта для малювання
private List<MyPoint> points = new List<MyPoint>(); // Список точок
private List<Edge> edges = new List<Edge>(); // Список ребер
private Graphics graphics; // Графічний контекст
// Константи для налаштування відображення
private const int Radius = 6;
private const int EdgeThickness = 2;
private const int PointLabelFontSize = 12;
private const int EdgeLabelFontSize = 10;
private const string FontName = "Arial";
// Конструктор форми
public Form1()
{
InitializeComponent();
// Ініціалізація графічних компонентів
bitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
graphics = Graphics.FromImage(bitmap);
// Налаштування DataGridView для точок
dataGridViewPoints.Columns.Add("pointNumber", "№");
dataGridViewPoints.Columns.Add("pointСoordinates", "Point");
dataGridViewPoints.Columns[0].Width = 30;
dataGridViewPoints.Columns[1].Width = 70;
// Налаштування DataGridView для матриці
dataGridViewMatrix.RowHeadersWidth = 50;
}
// Обчислення довжини ребра між двома точками
private int EdgeLength(MyPoint point1, MyPoint point2)
{
return (int) Math.Sqrt(Math.Pow(point1.X - point2.X, 2) + Math.Pow(point1.Y - point2.Y, 2));
}
// Малювання точки на графіці
private void DrawPoint(MyPoint point, string text)
{
// Малювання червоного кружечка
graphics.FillEllipse(new SolidBrush(Color.Red),
point.X - Radius, point.Y - Radius, Radius * 2, Radius * 2);
// Додавання текстової мітки
graphics.DrawString(text, new Font(FontName, PointLabelFontSize),
new SolidBrush(Color.Black), point.X + Radius, point.Y + Radius);
pictureBox.Image = bitmap;
}
// Заповнення матриці суміжності
private void FillMatrix(int number)
{
for (int i = 0; i < points.Count; i++)
{
for (int j = 0; j < points.Count; j++)
{
dataGridViewMatrix.Rows[i].Cells[j].Value = (i < j) ? number : 0;
}
}
}
// Генерація матриці суміжності
private void GenerateMatrix()
{
ClearMatrix();
// Додавання колонок до матриці
foreach (var point in points)
{
DataGridViewColumn column = new DataGridViewTextBoxColumn();
column.Name = $"{point.Id}";
column.Width = 25;
dataGridViewMatrix.Columns.Add(column);
}
// Додавання рядків до матриці
foreach (var point in points)
{
dataGridViewMatrix.Rows.Add();
dataGridViewMatrix.Rows[dataGridViewMatrix.Rows.Count - 1].HeaderCell.Value = $"{point.Id}";
}
FillMatrix(1);
// Центрування тексту в комірках
foreach (DataGridViewColumn column in dataGridViewMatrix.Columns)
{
column.DefaultCellStyle.Alignment = DataGridViewContentAlignment.MiddleCenter;
}
}
// Генерація списку ребер на основі матриці
private void GenerateEdges()
{
edges.Clear();
for (int i = 0; i < points.Count; i++)
{
for (int j = 0; j < points.Count; j++)
{
if (i != j && Convert.ToInt32(dataGridViewMatrix.Rows[i].Cells[j].Value) == 1)
{
MyPoint p1 = new MyPoint(points[i].Id, points[i].X, points[i].Y);
MyPoint p2 = new MyPoint(points[j].Id, points[j].X, points[j].Y);
edges.Add(new Edge(p1, p2, EdgeLength(p1, p2)));
}
}
}
}
// Алгоритм побудови мінімального кістякового дерева (алгоритм Прима)
private void ToMST()
{
if(edges.Count == 0)
return;
List<Edge> notUsedEdges = new List<Edge>(edges);
List<MyPoint> usedPoints = new List<MyPoint>();
List<MyPoint> notUsedPoints = new List<MyPoint>();
// Заповнення списку невикористаних точок
foreach (var edge in edges)
{
if (!notUsedPoints.Contains(edge.Point1))
notUsedPoints.Add(edge.Point1);
if (!notUsedPoints.Contains(edge.Point2))
notUsedPoints.Add(edge.Point2);
}
edges.Clear();
usedPoints.Add(notUsedPoints[0]);
notUsedPoints.RemoveAt(0);
// Основний цикл алгоритму Прима
while (notUsedPoints.Count > 0)
{
int minimumEdge = -1;
// Пошук мінімального ребра
for (int i = 0; i < notUsedEdges.Count; i++)
{
if ((usedPoints.IndexOf(notUsedEdges[i].Point1) != -1) && (notUsedPoints.IndexOf(notUsedEdges[i].Point2) != -1) ||
(usedPoints.IndexOf(notUsedEdges[i].Point2) != -1) && (notUsedPoints.IndexOf(notUsedEdges[i].Point1) != -1))
{
if (minimumEdge != -1)
{
if (notUsedEdges[i].Weight < notUsedEdges[minimumEdge].Weight)
minimumEdge = i;
}
else
minimumEdge = i;
}
}
// Додавання нової точки до дерева
if (usedPoints.IndexOf(notUsedEdges[minimumEdge].Point1) != -1)
{
usedPoints.Add(notUsedEdges[minimumEdge].Point2);
notUsedPoints.Remove(notUsedEdges[minimumEdge].Point2);
}
else
{
usedPoints.Add(notUsedEdges[minimumEdge].Point1);
notUsedPoints.Remove(notUsedEdges[minimumEdge].Point1);
}
edges.Add(notUsedEdges[minimumEdge]);
notUsedEdges.RemoveAt(minimumEdge);
}
FillMatrix(0);
// Оновлення матриці суміжності для MST
foreach (var edge in edges)
{
dataGridViewMatrix.Rows[edge.Point1.Id].Cells[edge.Point2.Id].Value = 1;
}
}
// Малювання всіх точок
private void DrawPoints()
{
for (int i = 0; i < points.Count; i++)
{
DrawPoint(points[i], $"{i}");
}
}
// Малювання всіх ребер
private void DrawEdges()
{
foreach (var edge in edges)
{
MyPoint p1 = edge.Point1;
MyPoint p2 = edge.Point2;
var label = EdgeLength(p1, p2).ToString();
var font = new Font(FontName, EdgeLabelFontSize);
var size = graphics.MeasureString(label, font, pictureBox.Size);
// Малювання лінії ребра
graphics.DrawLine(new Pen(Color.Chartreuse, EdgeThickness),
new Point(p1.X, p1.Y), new Point(p2.X, p2.Y));
// Додавання мітки з довжиною ребра
graphics.DrawString(label,
font, new SolidBrush(Color.Black),
(p1.X + p2.X) / 2 - size.Width / 2, (p1.Y + p2.Y) / 2 - size.Height / 2);
}
}
// Очищення графа
private void ClearGraph()
{
graphics.Clear(Color.White);
pictureBox.Image = bitmap;
points.Clear();
dataGridViewPoints.Rows.Clear();
}
// Очищення матриці
private void ClearMatrix()
{
dataGridViewMatrix.Rows.Clear();
dataGridViewMatrix.Columns.Clear();
}
// Обробник кліку на pictureBox для додавання нової точки
private void pictureBox_Click(object sender, EventArgs e)
{
int x = MousePosition.X - Location.X - pictureBox.Location.X - 8;
int y = MousePosition.Y - Location.Y - pictureBox.Location.Y - 32;
points.Add(new MyPoint(points.Count, x, y));
dataGridViewPoints.Rows.Add(points[points.Count - 1].Id, $"({x}; {y})");
DrawPoint(points[points.Count - 1], $"{points.Count - 1}");
}
// Обробник меню для генерації нового графа
private void newGraphToolStripMenuItem_Click(object sender, EventArgs e)
{
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges();
DrawEdges();
Invalidate();
}
// Обробник меню для очищення всього
private void clearToolStripMenuItem_Click(object sender, EventArgs e)
{
ClearGraph();
ClearMatrix();
}
// Обробник меню для генерації матриці
private void generateMatrixToolStripMenuItem_Click(object sender, EventArgs e)
{
GenerateMatrix();
}
// Обробник меню для побудови кістякового дерева
private void toSpanningToolStripMenuItem_Click(object sender, EventArgs e)
{
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges();
ToMST();
}
// Перевизначення методу малювання форми
protected override void OnPaint(PaintEventArgs e)
{
graphics.Clear(Color.White);
pictureBox.Image = bitmap;
DrawPoints();
DrawEdges();
base.OnPaint(e);
}
}
}