Алгоритм краскала

            Font ft = new Font("Times New Roman", 16);

            Size sz = new Size(8, 8);

int k = 0;

control();

e.Graphics.Clear(pictureBox1.BackColor);

            Graphics gr = e.Graphics;

foreach (Point pt in koord)

            {

e.Graphics.FillEllipse(Brushes.Gray, new Rectangle(pt, sz));

e.Graphics.DrawString((k + 1).ToString(), ft, Brushes.Gray, pt.X - 20, pt.Y - 20);

k++;

            }

for (short i = 0; i< n; i++)

for (short j = 0; j < n; j++)

if (a[i, j] != 0)

                    {

e.Graphics.DrawLine(Pens.Gray, pnt[i].X + 4, pnt[i].Y + 4, pnt[j].X + 4, pnt[j].Y + 4);

                    }

if (k >= n)

                button2.Enabled = true;

else

                button2.Enabled = false;

ft.Dispose();

       }

public void pictureBox1_MouseClick(object sender, MouseEventArgs e)

        {

MouseButtons mouse = e.Button;

if (mouse == MouseButtons.Left)

            {

koord.Add(e.Location);

            }

            n = koord.Count;

            numericUpDown1.Value = n;

pictureBox1.Invalidate();

        }

private void pictureBox2_Paint_1(object sender, PaintEventArgs e)

        {

if (koord.Count != n)

return;

Point[] pnt = (Point[])koord.ToArray(typeof(Point));

            Font ft = new Font("Times New Roman", 16);

            Size sz = new Size(8, 8);

int k = 0;

control();

e.Graphics.Clear(pictureBox2.BackColor);

            Graphics gr = e.Graphics;

foreach (Point pt in koord)

            {

e.Graphics.FillEllipse(Brushes.Gray, new Rectangle(pt, sz));

e.Graphics.DrawString((k + 1).ToString(), ft, Brushes.Gray, pt.X - 20, pt.Y - 20);

k++;

            }

for (short i = 0; i< n; i++)

for (short j = 0; j < n; j++)

if (a1[i, j] != 0)

                    {

e.Graphics.DrawLine(Pens.Gray, pnt[i].X + 4, pnt[i].Y + 4, pnt[j].X + 4, pnt[j].Y + 4);

                    }

ft.Dispose();

        }

private void button2_EnabledChanged(object sender, EventArgs e)

{

        }       

      }

    }

 

Рис. 4 Начальный граф

 

Рис. 5Остовный лес

 

 

 

 

 

 

3 Описание разработанного  программного обеспечения.

 

Эта программа  строит остовный лес для любого неориентированного графа по Алгоритму Краскала. Ниже размещено его формальное описание. 
1. Множество ребер искомого остовного дерева полагаем пустым (H = null); 
2. Формируем множество V = {{v1}, ... , {vn}}, элементами которого являются множества вершин, соответствующих компонентам искомого остовного леса. Каждая такая компонента состоит из единственной вершины; 
3. Сортируем множество ребер Е исходного графа по возрастанию. Далее множество Е будет восприниматься нами как очередь, т. е. в любой момент из этой очереди может быть извлечено только первое ребро (принцип "первым пришел - первым ушел"); 
4. Если множество Vs содержит более одного элемента (т. е. остовный лес состоит из нескольких компонент) и множество ребер Е не пусто, переходим на шаг 5, в противном случае - на шаг 7; 
5. Извлекаем из очереди Е ребро е. Если концы этого ребра принадлежат разным элементам из множества V (т. е. разным компонентам), переходим к шагу 6, иначе - отбрасываем извлеченное ребро и переходим к шагу 4; 
6. Обьединяем множества вершин Vi и Vj (т. е. обьединяем соединенные данным ребром компоненты в одну), после чего добавляем ребро е в множество Н. Возвращаемся на шаг 4. 
7. Прекращаем работу. Множество Н является множеством ребер искомого остовного леса (дерева).

 

 

 

 

 

 

 

 

 

Заключение.

В ходе выполнения данного курсового проекта была разработана программа для реализации алгоритма Краскала. Также теоретически и экспериментально была получена  трудоемкость данного алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы.

1)Шилдт Г. Самоучитель С# - 3 издание  – БХВ-Петербург, 2009

2) http://rain.ifmo.ru/cat/view.php/theory/math/kruskal

3) http://comp-science.narod.ru/Progr/Rekursia.html