Нехай задано зважений неорієнтований зв'язний граф з 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();
// Ініціалізація бітової карти розміром з PictureBox
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; // Оновлюємо зображення в PictureBox
}
// Заповнення матриці суміжності заданим числом (для демонстрації)
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++)
{
// Якщо в матриці на перетині i-го рядка та j-го стовпця стоїть 1 і це не петля
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);
}
// Очищаємо список ребер (будемо додавати тільки ребра MST)
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)
{
// Якщо точка1 вже використана, додаємо точку2
usedPoints.Add(notUsedEdges[minimumEdge].Point2);
notUsedPoints.Remove(notUsedEdges[minimumEdge].Point2);
}
else
{
// Інакше додаємо точку1
usedPoints.Add(notUsedEdges[minimumEdge].Point1);
notUsedPoints.Remove(notUsedEdges[minimumEdge].Point1);
}
// Додаємо вибране ребро до списку ребер MST
edges.Add(notUsedEdges[minimumEdge]);
// Видаляємо використане ребро зі списку невикористаних
notUsedEdges.RemoveAt(minimumEdge);
}
// Оновлюємо матрицю суміжності: обнуляємо всі значення, потім встановлюємо 1 для ребер MST
FillMatrix(0);
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)
{
// Обчислюємо координати кліку з урахуванням положення PictureBox на формі
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}");
}
// Обробник меню "Generate" (побудова графа)
private void newGraphToolStripMenuItem_Click(object sender, EventArgs e)
{
// Якщо матриця ще не створена або її розмір менший за кількість вершин, генеруємо її
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges(); // Створюємо ребра на основі матриці
DrawEdges(); // Малюємо ребра
Invalidate(); // Оновлюємо відображення
}
// Обробник меню "Clear" (повне очищення)
private void clearToolStripMenuItem_Click(object sender, EventArgs e)
{
ClearGraph(); // Очищаємо граф
ClearMatrix(); // Очищаємо матрицю
}
// Обробник меню "Generate" (генерація матриці)
private void generateMatrixToolStripMenuItem_Click(object sender, EventArgs e)
{
GenerateMatrix();
}
// Обробник меню "To Spanning Tree" (побудова кістякового дерева)
private void toSpanningToolStripMenuItem_Click(object sender, EventArgs e)
{
// Якщо матриця не відповідає кількості вершин, генеруємо її
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges(); // Оновлюємо список ребер
ToMST(); // Запускаємо алгоритм побудови MST
Invalidate(); // Перемальовуємо форму
}
// Перевизначений метод OnPaint для власного малювання
protected override void OnPaint(PaintEventArgs e)
{
graphics.Clear(Color.White); // Очищаємо графічний контекст
pictureBox.Image = bitmap; // Встановлюємо очищений bitmap
DrawPoints(); // Малюємо вершини
DrawEdges(); // Малюємо ребра
base.OnPaint(e);
}
}
}