Простими словами, обхід графа — це перехід від однієї його вершини до іншої у пошуку властивостей зв'язків цих вершин.
Двома основними алгоритмами обходу графа є пошук у глибину (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;
}
}
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;
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;
// Додавання випадаючих списків для вибору вершин
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++)
{
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;
// Ініціалізація масивів для BFS
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);
}
}
}
// Відновлення шляху
bfsPathEdges.Clear();
List<int> path = new List<int>();
int current = endVertexId;
// Перевірка чи існує шлях
if (!visited[endVertexId])
{
MessageBox.Show("Шлях не знайдено між обраними вершинами");
return;
}
// Відновлення шляху від кінцевої до початкової вершини
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));
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++)
{
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)
{
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();
}
}
// Обробник меню для генерації нового графа
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();
}
// Обробник меню для знаходження шляху BFS
private void findBFSPathToolStripMenuItem_Click(object sender, EventArgs e)
{
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges();
BFSAlgorithm();
Invalidate();
}
// Перевизначення методу малювання форми
protected override void OnPaint(PaintEventArgs e)
{
graphics.Clear(Color.White);
pictureBox.Image = bitmap;
DrawPoints();
DrawEdges();
base.OnPaint(e);
}
}
}