Простими словами, обхід графа — це перехід від однієї його вершини до іншої у пошуку властивостей зв'язків цих вершин.
Двома основними алгоритмами обходу графа є пошук у глибину (Depth-First Search, DFS) та пошук у ширину (Breadth-First Search, BFS).
Кожна вершина, що розглядається, може перебувати в одному з 3 станів:
Суть алгоритму полягає в тому, щоб спочатку переглядати стартову вершину 0, потім вершини, що знаходяться на відстані 1 від неї, і так далі шарами. Для цього використовується черга Q, у яку спочатку додається стартова вершина.
Потім повторюються наступні ітерації: поки черга не порожня, з її початку береться чергова вершина, переглядаються всі її сусіди, і якщо якісь з них ще не додані до черги, вони додаються в кінець черги.
Процедура BFS будує у процесі обходу графа дерево пошуку в ширину. Дерево представлене за допомогою поля p у кожній вершині. Формально, для графа G = (V, Е) з початковою вершиною s визначається підграф попередників, який є деревом пошуку в ширину, якщо Vn складається з вершин, досяжних з s, і для всіх v ∈ Vn у Gn є єдиний простий шлях з s до v, який одночасно є найкоротшим шляхом у G.
// Структура для представлення точки (вершини) графа
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;
}
}
// Структура для представлення ребра графа
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;
}
}
namespace GraphVisualization
{
partial class Form1
{
///
/// Required designer variable.
///
private System.ComponentModel.IContainer components = null;
///
/// Clean up any resources being used.
///
/// true if managed resources should be disposed; otherwise, false.
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}
#region Windows Form Designer generated code
///
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
///
private void InitializeComponent()
{
this.menuStrip1 = new System.Windows.Forms.MenuStrip();
this.graphToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.newGraphToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.clearToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.matrixToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.generateMatrixToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.findBFSPathToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.pictureBox = new System.Windows.Forms.PictureBox();
this.dataGridViewPoints = new System.Windows.Forms.DataGridView();
this.dataGridViewMatrix = new System.Windows.Forms.DataGridView();
this.labelPoints = new System.Windows.Forms.Label();
this.labelMatrix = new System.Windows.Forms.Label();
this.comboBoxStartVertex = new System.Windows.Forms.ComboBox();
this.comboBoxEndVertex = new System.Windows.Forms.ComboBox();
this.labelStartVertex = new System.Windows.Forms.Label();
this.labelEndVertex = new System.Windows.Forms.Label();
this.menuStrip1.SuspendLayout();
((System.ComponentModel.ISupportInitialize)(this.pictureBox)).BeginInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewPoints)).BeginInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewMatrix)).BeginInit();
this.SuspendLayout();
//
// menuStrip1
//
this.menuStrip1.Items.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.graphToolStripMenuItem,
this.matrixToolStripMenuItem});
this.menuStrip1.Location = new System.Drawing.Point(0, 0);
this.menuStrip1.Name = "menuStrip1";
this.menuStrip1.Size = new System.Drawing.Size(980, 24);
this.menuStrip1.TabIndex = 0;
this.menuStrip1.Text = "menuStrip1";
//
// graphToolStripMenuItem
//
this.graphToolStripMenuItem.DropDownItems.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.newGraphToolStripMenuItem,
this.clearToolStripMenuItem});
this.graphToolStripMenuItem.Name = "graphToolStripMenuItem";
this.graphToolStripMenuItem.Size = new System.Drawing.Size(51, 20);
this.graphToolStripMenuItem.Text = "Graph";
//
// newGraphToolStripMenuItem
//
this.newGraphToolStripMenuItem.Name = "newGraphToolStripMenuItem";
this.newGraphToolStripMenuItem.Size = new System.Drawing.Size(121, 22);
this.newGraphToolStripMenuItem.Text = "Generate";
this.newGraphToolStripMenuItem.Click += new System.EventHandler(this.newGraphToolStripMenuItem_Click);
//
// clearToolStripMenuItem
//
this.clearToolStripMenuItem.Name = "clearToolStripMenuItem";
this.clearToolStripMenuItem.Size = new System.Drawing.Size(121, 22);
this.clearToolStripMenuItem.Text = "Clear";
this.clearToolStripMenuItem.Click += new System.EventHandler(this.clearToolStripMenuItem_Click);
//
// matrixToolStripMenuItem
//
this.matrixToolStripMenuItem.DropDownItems.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.generateMatrixToolStripMenuItem,
this.findBFSPathToolStripMenuItem});
this.matrixToolStripMenuItem.Name = "matrixToolStripMenuItem";
this.matrixToolStripMenuItem.Size = new System.Drawing.Size(53, 20);
this.matrixToolStripMenuItem.Text = "Matrix";
//
// generateMatrixToolStripMenuItem
//
this.generateMatrixToolStripMenuItem.Name = "generateMatrixToolStripMenuItem";
this.generateMatrixToolStripMenuItem.Size = new System.Drawing.Size(180, 22);
this.generateMatrixToolStripMenuItem.Text = "Generate";
this.generateMatrixToolStripMenuItem.Click += new System.EventHandler(this.generateMatrixToolStripMenuItem_Click);
//
// findBFSPathToolStripMenuItem
//
this.findBFSPathToolStripMenuItem.Name = "findBFSPathToolStripMenuItem";
this.findBFSPathToolStripMenuItem.Size = new System.Drawing.Size(180, 22);
this.findBFSPathToolStripMenuItem.Text = "Find BFS Path";
this.findBFSPathToolStripMenuItem.Click += new System.EventHandler(this.findBFSPathToolStripMenuItem_Click);
//
// pictureBox
//
this.pictureBox.BorderStyle = System.Windows.Forms.BorderStyle.FixedSingle;
this.pictureBox.Location = new System.Drawing.Point(12, 27);
this.pictureBox.Name = "pictureBox";
this.pictureBox.Size = new System.Drawing.Size(400, 400);
this.pictureBox.TabIndex = 1;
this.pictureBox.TabStop = false;
this.pictureBox.Click += new System.EventHandler(this.pictureBox_Click);
//
// dataGridViewPoints
//
this.dataGridViewPoints.AllowUserToAddRows = false;
this.dataGridViewPoints.AllowUserToDeleteRows = false;
this.dataGridViewPoints.AllowUserToResizeColumns = false;
this.dataGridViewPoints.AllowUserToResizeRows = false;
this.dataGridViewPoints.ColumnHeadersHeightSizeMode = System.Windows.Forms.DataGridViewColumnHeadersHeightSizeMode.AutoSize;
this.dataGridViewPoints.Enabled = false;
this.dataGridViewPoints.Location = new System.Drawing.Point(420, 43);
this.dataGridViewPoints.Name = "dataGridViewPoints";
this.dataGridViewPoints.Size = new System.Drawing.Size(160, 384);
this.dataGridViewPoints.TabIndex = 2;
//
// dataGridViewMatrix
//
this.dataGridViewMatrix.AllowUserToAddRows = false;
this.dataGridViewMatrix.AllowUserToDeleteRows = false;
this.dataGridViewMatrix.AllowUserToResizeColumns = false;
this.dataGridViewMatrix.AllowUserToResizeRows = false;
this.dataGridViewMatrix.ColumnHeadersHeightSizeMode = System.Windows.Forms.DataGridViewColumnHeadersHeightSizeMode.AutoSize;
this.dataGridViewMatrix.Location = new System.Drawing.Point(586, 43);
this.dataGridViewMatrix.Name = "dataGridViewMatrix";
this.dataGridViewMatrix.Size = new System.Drawing.Size(384, 384);
this.dataGridViewMatrix.TabIndex = 3;
//
// labelPoints
//
this.labelPoints.AutoSize = true;
this.labelPoints.Location = new System.Drawing.Point(482, 27);
this.labelPoints.Name = "labelPoints";
this.labelPoints.Size = new System.Drawing.Size(36, 13);
this.labelPoints.TabIndex = 4;
this.labelPoints.Text = "Points";
//
// labelMatrix
//
this.labelMatrix.AutoSize = true;
this.labelMatrix.Location = new System.Drawing.Point(735, 27);
this.labelMatrix.Name = "labelMatrix";
this.labelMatrix.Size = new System.Drawing.Size(87, 13);
this.labelMatrix.TabIndex = 5;
this.labelMatrix.Text = "Adjacency matrix";
//
// comboBoxStartVertex
//
this.comboBoxStartVertex.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
this.comboBoxStartVertex.FormattingEnabled = true;
this.comboBoxStartVertex.Location = new System.Drawing.Point(420, 450);
this.comboBoxStartVertex.Name = "comboBoxStartVertex";
this.comboBoxStartVertex.Size = new System.Drawing.Size(160, 21);
this.comboBoxStartVertex.TabIndex = 6;
this.comboBoxStartVertex.SelectedIndexChanged += new System.EventHandler(this.comboBoxStartVertex_SelectedIndexChanged);
//
// comboBoxEndVertex
//
this.comboBoxEndVertex.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
this.comboBoxEndVertex.FormattingEnabled = true;
this.comboBoxEndVertex.Location = new System.Drawing.Point(586, 450);
this.comboBoxEndVertex.Name = "comboBoxEndVertex";
this.comboBoxEndVertex.Size = new System.Drawing.Size(160, 21);
this.comboBoxEndVertex.TabIndex = 7;
this.comboBoxEndVertex.SelectedIndexChanged += new System.EventHandler(this.comboBoxEndVertex_SelectedIndexChanged);
//
// labelStartVertex
//
this.labelStartVertex.AutoSize = true;
this.labelStartVertex.Location = new System.Drawing.Point(420, 434);
this.labelStartVertex.Name = "labelStartVertex";
this.labelStartVertex.Size = new System.Drawing.Size(62, 13);
this.labelStartVertex.TabIndex = 8;
this.labelStartVertex.Text = "Start Vertex";
//
// labelEndVertex
//
this.labelEndVertex.AutoSize = true;
this.labelEndVertex.Location = new System.Drawing.Point(586, 434);
this.labelEndVertex.Name = "labelEndVertex";
this.labelEndVertex.Size = new System.Drawing.Size(59, 13);
this.labelEndVertex.TabIndex = 9;
this.labelEndVertex.Text = "End Vertex";
//
// Form1
//
this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
this.ClientSize = new System.Drawing.Size(980, 483);
this.Controls.Add(this.labelEndVertex);
this.Controls.Add(this.labelStartVertex);
this.Controls.Add(this.comboBoxEndVertex);
this.Controls.Add(this.comboBoxStartVertex);
this.Controls.Add(this.labelMatrix);
this.Controls.Add(this.labelPoints);
this.Controls.Add(this.dataGridViewMatrix);
this.Controls.Add(this.dataGridViewPoints);
this.Controls.Add(this.pictureBox);
this.Controls.Add(this.menuStrip1);
this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;
this.MainMenuStrip = this.menuStrip1;
this.Name = "Form1";
this.Text = "Graph Visualization - BFS Algorithm";
this.menuStrip1.ResumeLayout(false);
this.menuStrip1.PerformLayout();
((System.ComponentModel.ISupportInitialize)(this.pictureBox)).EndInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewPoints)).EndInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewMatrix)).EndInit();
this.ResumeLayout(false);
this.PerformLayout();
}
#endregion
private System.Windows.Forms.MenuStrip menuStrip1;
private System.Windows.Forms.ToolStripMenuItem graphToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem newGraphToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem clearToolStripMenuItem;
private System.Windows.Forms.PictureBox pictureBox;
private System.Windows.Forms.DataGridView dataGridViewPoints;
private System.Windows.Forms.DataGridView dataGridViewMatrix;
private System.Windows.Forms.Label labelPoints;
private System.Windows.Forms.Label labelMatrix;
private System.Windows.Forms.ToolStripMenuItem matrixToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem generateMatrixToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem findBFSPathToolStripMenuItem;
private System.Windows.Forms.ComboBox comboBoxStartVertex;
private System.Windows.Forms.ComboBox comboBoxEndVertex;
private System.Windows.Forms.Label labelStartVertex;
private System.Windows.Forms.Label labelEndVertex;
}
}
Основна логіка програми знаходиться у файлі Form1.cs. Нижче наведено код з докладними коментарями.
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 List<Edge> bfsPathEdges = new List<Edge>(); // Ребра, що входять у знайдений шлях BFS
private Graphics graphics; // Графічний контекст для малювання
private int startVertexId = -1; // Ідентифікатор початкової вершини для BFS
private int endVertexId = -1; // Ідентифікатор кінцевої вершини для BFS
// Константи для налаштування відображення
private const int Radius = 6; // Радіус кола вершини
private const int EdgeThickness = 2; // Товщина звичайного ребра
private const int BFSPathThickness = 3; // Товщина ребра шляху BFS
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; // Ширина заголовків рядків
// Налаштування випадаючих списків для вибору вершин
comboBoxStartVertex.DropDownStyle = ComboBoxStyle.DropDownList;
comboBoxEndVertex.DropDownStyle = ComboBoxStyle.DropDownList;
}
// Обчислення довжини ребра між двома точками (теорема Піфагора)
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, Color color)
{
// Малюємо зафарбоване коло
graphics.FillEllipse(new SolidBrush(color),
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;
}
// Оновлюємо випадаючі списки вибору вершин
UpdateVertexComboBoxes();
}
// Оновлення випадаючих списків для вибору початкової та кінцевої вершин
private void UpdateVertexComboBoxes()
{
comboBoxStartVertex.Items.Clear();
comboBoxEndVertex.Items.Clear();
// Додаємо номер кожної вершини
foreach (var point in points)
{
comboBoxStartVertex.Items.Add($"{point.Id}");
comboBoxEndVertex.Items.Add($"{point.Id}");
}
// Встановлюємо перший елемент за замовчуванням
if (comboBoxStartVertex.Items.Count > 0)
comboBoxStartVertex.SelectedIndex = 0;
if (comboBoxEndVertex.Items.Count > 0)
comboBoxEndVertex.SelectedIndex = 0;
}
// Генерація списку ребер на основі матриці суміжності
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)));
}
}
}
}
// Алгоритм пошуку в ширину (BFS) для знаходження найкоротшого шляху
private void BFSAlgorithm()
{
// Перевірка, чи є ребра та обрані вершини
if (edges.Count == 0 || startVertexId == -1 || endVertexId == -1)
return;
// Масив для відстеження відвіданих вершин
bool[] visited = new bool[points.Count];
// Масив для зберігання попередньої вершини у шляху
int[] previous = new int[points.Count];
// Черга для обробки вершин
Queue<int> queue = new Queue<int>();
// Ініціалізація масивів
for (int i = 0; i < points.Count; i++)
{
visited[i] = false;
previous[i] = -1;
}
// Починаємо BFS з початкової вершини
visited[startVertexId] = true;
queue.Enqueue(startVertexId);
while (queue.Count > 0)
{
int currentVertex = queue.Dequeue(); // Беремо вершину з початку черги
// Якщо досягли кінцевої вершини, виходимо з циклу
if (currentVertex == endVertexId)
break;
// Переглядаємо всі ребра, щоб знайти сусідів поточної вершини
foreach (var edge in edges)
{
int neighbor = -1;
// Визначаємо, чи є поточна вершина одним із кінців ребра, і знаходимо інший кінець
if (edge.Point1.Id == currentVertex)
neighbor = edge.Point2.Id;
else if (edge.Point2.Id == currentVertex)
neighbor = edge.Point1.Id;
// Якщо знайшли сусіда, якого ще не відвідали
if (neighbor != -1 && !visited[neighbor])
{
visited[neighbor] = true; // Позначаємо як відвідану
previous[neighbor] = currentVertex; // Запам'ятовуємо, з якої вершини прийшли
queue.Enqueue(neighbor); // Додаємо в чергу для подальшої обробки
}
}
}
// Очищаємо попередній список ребер шляху BFS
bfsPathEdges.Clear();
// Якщо кінцева вершина не була досягнута, шляху не існує
if (!visited[endVertexId])
{
MessageBox.Show("Шлях не знайдено між обраними вершинами");
return;
}
// Відновлення шляху від кінцевої вершини до початкової
List<int> path = new List<int>();
int current = endVertexId;
while (current != -1)
{
path.Add(current); // Додаємо поточну вершину до шляху
current = previous[current]; // Переходимо до попередньої
}
path.Reverse(); // Перевертаємо список, щоб шлях йшов від початку до кінця
// Знаходимо ребра, що відповідають знайденому шляху
for (int i = 0; i < path.Count - 1; i++)
{
int from = path[i];
int to = path[i + 1];
// Шукаємо ребро між двома послідовними вершинами шляху
var pathEdge = edges.FirstOrDefault(e =>
(e.Point1.Id == from && e.Point2.Id == to) ||
(e.Point1.Id == to && e.Point2.Id == from));
// Якщо ребро знайдено, додаємо його до списку BFS-шляху
if (pathEdge.Point1.Id != -1)
{
bfsPathEdges.Add(pathEdge);
}
}
// Виводимо інформацію про знайдений шлях
MessageBox.Show($"Шлях знайдено! Довжина шляху: {path.Count - 1} ребер\n" +
$"Шлях: {string.Join(" → ", path)}");
}
// Малювання всіх вершин графа
private void DrawPoints()
{
for (int i = 0; i < points.Count; i++)
{
// Визначаємо колір вершини залежно від її ролі у BFS
Color pointColor = Color.Red;
if (i == startVertexId)
pointColor = Color.Green; // Початкова вершина - зелена
else if (i == endVertexId)
pointColor = Color.Blue; // Кінцева вершина - синя
DrawPoint(points[i], $"{i}", pointColor);
}
}
// Малювання всіх ребер графа
private void DrawEdges()
{
foreach (var edge in edges)
{
// Перевіряємо, чи належить ребро до знайденого BFS-шляху
bool isBFSPath = bfsPathEdges.Any(pe =>
(pe.Point1.Id == edge.Point1.Id && pe.Point2.Id == edge.Point2.Id) ||
(pe.Point1.Id == edge.Point2.Id && pe.Point2.Id == edge.Point1.Id));
// Встановлюємо колір і товщину залежно від належності до шляху
Color edgeColor = isBFSPath ? Color.Red : Color.Chartreuse;
int thickness = isBFSPath ? BFSPathThickness : EdgeThickness;
MyPoint p1 = edge.Point1;
MyPoint p2 = edge.Point2;
var label = edge.Weight.ToString();
var font = new Font(FontName, EdgeLabelFontSize);
var size = graphics.MeasureString(label, font, pictureBox.Size);
// Малюємо лінію ребра
graphics.DrawLine(new Pen(edgeColor, thickness),
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();
bfsPathEdges.Clear();
startVertexId = -1;
endVertexId = -1;
comboBoxStartVertex.Items.Clear();
comboBoxEndVertex.Items.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}", Color.Red);
}
// Обробник зміни вибору початкової вершини
private void comboBoxStartVertex_SelectedIndexChanged(object sender, EventArgs e)
{
if (comboBoxStartVertex.SelectedIndex >= 0)
{
startVertexId = comboBoxStartVertex.SelectedIndex;
Invalidate(); // Перемальовуємо форму
}
}
// Обробник зміни вибору кінцевої вершини
private void comboBoxEndVertex_SelectedIndexChanged(object sender, EventArgs e)
{
if (comboBoxEndVertex.SelectedIndex >= 0)
{
endVertexId = comboBoxEndVertex.SelectedIndex;
Invalidate(); // Перемальовуємо форму
}
}
// Обробник меню "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();
}
// Обробник меню "Find BFS Path"
private void findBFSPathToolStripMenuItem_Click(object sender, EventArgs e)
{
// Якщо матриця не відповідає кількості вершин, генеруємо її заново
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges(); // Оновлюємо список ребер
BFSAlgorithm(); // Запускаємо алгоритм BFS
Invalidate(); // Перемальовуємо
}
// Перевизначений метод OnPaint для власного малювання
protected override void OnPaint(PaintEventArgs e)
{
graphics.Clear(Color.White); // Очищаємо графічний контекст
pictureBox.Image = bitmap; // Встановлюємо очищений bitmap
DrawPoints(); // Малюємо вершини
DrawEdges(); // Малюємо ребра
base.OnPaint(e);
}
}
}