Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Введение

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.

Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра — это пары городов, между которыми есть маршрут, а вес ребра равен стоимости проезда по соответствующему маршруту.

Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:

- Алгоритм Прима;

- Алгоритм Краскала;

- Алгоритм Борувки.

В данной курсовой работе подробно будет рассмотрен алгоритм Краскала.

1 Анализ и теоретическое исследование алгоритма.

1.1 Постановка задачи.

В ходе выполнения данного курсового проекта необходимо разработать программный код построения минимального остовного дерева по алгоритму Краскала. Экспериментально и теоретически вычислить среднюю трудоемкость алгоритма, затем сравнить полученные значения.

1.2 Основные понятия теории графов.

Граф – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий(геометрический способ задания графа – см. рисунок 1). Кружки называются вершинами графа, линии со стрелками – дугами, безстрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линииявляются дугами) называется ориентированным.

Рис. 1. Пример графа

Теория графов может рассматриваться как раздел дискретной математики (точнее – теории множеств), и формальное определение графа таково: задано конечное множество X, состоящее из nэлементов (X = {1, 2, ..., n}), называемых вершинами графа, и подмножество V декартова произведения , то есть называется совокупность (X, V) (неориентированным графом называется совокупность множества X и множества неупорядоченныхпар элементов, каждый из которых принадлежит множеству X).Дугу между вершинами i и j, i, j X, будем обозначать (i, j). Число дуг графа будем обозначать m (V =

Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющимивершины из этого множества. Если из графа удалить часть ребер(дуг), то получим частичный граф.

Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вершинам. Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь – путь, в котором ни одна дуга не встречается дважды. Элементарный путь – путь, в котором ни одна вершина не встречается дважды. Контур – путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы). Граф, для которого из (i, j) V следует (j, i) V называетсясимметрическим. Если из (i, j) V следует, что (j, i) V, то соответствующий граф называется антисимметрическим.Цепью называется множество ребер (в неориентированномграфе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого.Замкнутаяцепь называется циклом.Если любые две вершины графа можно соединить цепью, тограф называется связным. Если граф не является связным, то егоможно разбить на связные подграфы, называемые компонентами. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединитьпутем, то граф называется сильно связным. Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n – 1, а число висячих вершин равно .

1.3 Минимальные остовные деревья.

Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.

При разработке ,например, электронных схем зачастую необходимо электрически соединить контакты нескольких компонентов. Для соединения множества из n контактов можем использовать некоторую компоновку из n-1 проводов, каждый из которых соединяет два контакта. Обычно желательно получить компоновку, которая использует минимальное количество провода.

Мы можем смоделировать эту задачу при помощи связного неориентированного графа G = (V, E), где V-множество контактов, E-множество возможных соединения между парами контактов, и для каждого ребра

(u,v) ∈E задан вес w (u,v), определяющий стоимость (количество необходимого провода) соединения u и v. Нам нужно найти ациклическое подмножество TE, которое соединяет все вершины и чей общий вес минимален. Поскольку множество Т ациклическое и связывает ве вершины, оно должно образовать дерево, которое мы назовем остовным деревом графа G. Задачу поиска дерева Т мы назовем задачей поиска минимального остовного дерева. На рис.2 Показан пример связного графа и его минимального остовного дерева. На ребрах указан их вес , а ребра минимального остовного дерева отдельно выделены цветом. Общий вес показанного дерева равен 37.

Рис. 2 Минимальное оставное дерево связанного графа.

Приведенное дерево не единственное: удалин ребро (b, c) и заменив его ребром (a, h), мы получин другое остовное дерево с тем же весом 37.

1.4 Построение минимального остовного дерева.

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадной стратегии. Итак, пусть дан связный неориентированный граф G=(V;E) c n вершинами и весовая функция w: E → R.

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграфА исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u,v) выбирается так, чтобы не нарушить этого свойства: A∪ {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

Вот как выглядит общий алгоритм построения минимального остовного дерева:

MST-GENERIC(G,w)
1: A ← 0
2: while (пока) A не является остовом
3: do найти безопасное ребро (u,v) ∈E для A
4: A ← A∪ {(u,v)}
5: returnA

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). Таким образом цикл выполняется (n-1) раз.

Далее приводится общее правило отыскания безопасных ребер. Для этого доказана теорема, которая поможет находить безопасные ребра. Предварительно докажем маленькую лемму:

Лемма: пусть Т – минимальное остовное дерево. Тогда любое ребро е из T – безопасное.
Док-во: в Т – (n-1) ребро. На каждом шаге Generic-MST мы добавляли одно безопасное ребро. Всего выполнено (n-1) шагов, следовательно, все ребра в T – безопасные по определению.

Теорема: Пусть G(V;E) – связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным.
Док-во: Пусть e=(u,v) – минимальное по весу ребро из E(K). Пусть минимальный остов T не содержит e (в противном случае доказываемое утверждение очевидно по приведенной выше лемме). Т.к. T связен, в нем существует некоторый (единственный) ациклический путь p из u в v, и e замыкает его в цикл. Поскольку один из концов e лежит в K, а другой в V \ K, в пути p существует хотя бы одно ребро e'=(x,y), которое обладает тем же свойством. Это ребро не лежит в A, т.к. в A пока что нет ребер между K и V \ K. Удалим из T ребро e' и добавим e. Так как w(e') <w(e), мы получим остовное дерево T', суммарный вес которого меньше суммарного веса T. Таким образом, T не является минимальным остовом. Противоречие. Следовательно, T содержит e.

В связи с приведенной теоремой введем следующее

Определение.Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

1.5 Теоретическое исследование Алгоритм Краскала.

Алгоритм Краскала объединяет вершины графа в несколько связных компонент, каждая из которых является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным. Безопасность ребра гарантируется ранее доказанной теоремой о безопасных ребрах. Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

Остается понять, как реализовать выбор безопасного ребра на каждом шаге. Для этого в алгоритме Краскала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

Удобно использовать для хранения компонент структуры данных для непересекающихся множеств, как, например, списки или, что лучше, лес непересекающихся множеств со сжатием путей и объединением по рангу (один из самых быстрых известных методов). Элементами множеств являются вершины графа, каждое множество содержит вершины одной связной компоненты. Для работы с множествами используются следующие процедуры:

Make-Set(v)	Создание множества из набора вершин
Find-Set(v)	Возвращает множество, содержащее данную вершину
Union(u,v)	Объединяет множества, содержащие данные вершины

Общая схема алгоритма выглядит так:

MST-KRUSKAL(G,w)
1: A ← 0
2: for each (для каждой) вершины v∈V[G]
3:     do Make-Set(v)
4: упорядочить ребра по весам
5: for (u,v) ∈E (в порядке возрастания веса)
6:     do if Find-Set(u) ≠ Find-Set(v) then
7:         A ← A∪ {(u,v)}
8:         Union(u,v)
9: returnA

Пример:

На рисунках К1-К8 представлена работа алгоритма.

Рис. К1. Начальная фаза. Минимальный покрывающий лес пуст.	Рис. К2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.
Рис. К3. Следующее безопасное ребро с весом 6. Добавляем его.	Рис. К4.
Рис. К5.	Рис. К6.
Рис. К7.	Рис. К8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Подсчитаем время работы алгоритма. Будем считать, что для хранения непересекающихся множеств используется метод с объединением по рангу и сжатием путей, т.к. это самый быстрый способ из известных на сегодняшний день. Инициализация занимает время O(V), упорядочение ребер в строке 4 – O(ElogE). Далее производится O(E) операций, в совокупности занимающих время O(Eα’(E,V)), где α’ - функция, обратная к функции Аккермана .Поскольку α’(E,V) = o(logE), общее время работы алгоритма Крускала составляет O(ElogE) (основное время уходит на сортировку).

1.6 Теоретическая оценка трудоемкости алгоритма Краскала.

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

Под элементарными операциями языка высокого уровня, будем понимать операции которые могут быть представлены в виде элементарных конструкций данного языка (но не обязательно в виде одной машинной команды), а именно за одну элементарную операцию будем считать следующие:

1) операцию присваивания a¬b;

2) операцию индексации массива a[i];

3) арифметические операции *,/,-,+;

4) операции сравнения a<b;

5) логические операции or,and,not.

Отметим, что неявно в операцию сравнения входит машинная команда перехода в конструкции ifthenelse:

F _{«ветвление»} = f_then * p +f_else * (1-p).

Цикл не является элементарной операцией, т.к. может быть представлен в виде;

fori¬1 to N

тело Û

end;

Таким образом конструкция цикла требует 1+3*N элементарных операций:

F_«цикл» = 1+3*N+N*f_{«тела
цикла».}

2 Разработка технологии экспериментального исследования алгоритм.

2.1 Блок схема программы и ее описание.

Рис.3.Блок-схема алгоритма задачи моделирования

Описание блок-схемы алгоритма задачи моделирования

Блок 1. Ввод матрицы весов ребер графа. Запись графа в память компьютера осуществляется при помощи двумерного массива, который служит матрицей весов ребер графа.

Блок 2. Ввод вершины поиска. После заполнения матрицы весов пользователем программа автоматически определяет вершину начала построения остова.

Блок 3. Поиск ребра минимального веса среди инцидентных n ребер. Программа анализирует матрицу весов и находит ребро с минимальным весом. Найденное ребро сохраняется в переменнуюmin.

Блок 4. Формирование остова. Формируется остов.

Блок 5.Выбор новой инцидентной вершины. Помечается новая вершина, инцидентная ребру, - переменная m.

Блок 6. Все вершины графа помечены. Если все вершины графа помечены, то поиск остова заканчивается. Если нет, то среди инцидентных помеченным вершинам ребер, за исключением ребер остова и ребер, образующих в остов цикл, происходит поиск ребра минимального веса min и построение остова.

Блок 7. Вывод остова. После того как все вершины графа помечены, на монитор пользователя выводится остов минимального веса.

Блок 8. Инцидентные помеченным вершинам ребра. Если есть такие ребра, то программа анализирует найденные ребра, если нет инцидентных ребер, то программа переходит к Блоку 6.

Блок 9. Ребра остова. Найденное ребро не используется в остове, то программа переходит к Блоку 10, а если используется, то переходит к Блоку 6.

Блок 10. Образует ребро в остове цикл, если да то программа переходит к Блоку 6. Если ребро не образует в остове цикл, то программа переходит к Блоку11.

Блок 11. Нахождение ребра минимального веса. Программа анализирует оставшиеся инцидентные ребра выбранной вершине и переходит к Блоку 12.

Блок 12. Формирование остова. Программа формирует полученный остов, проверяется связанность ребер с вершинами графа, за это отвечает массивсвязанности ar[jmin, imin], если он равен единицам, то все ребра связаны с вершинами, если он не равен единице, то продолжается формирование остова.

Блок 13. Выбор новой инцидентной вершины. Помечается новая вершина графа, программа переходит к Блоку 6.

2.2 Код программы.

using System;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Windows.Forms;

usingSystem.Xml;

usingSystem.Collections;

namespace WindowsFormsApplication4

{

public partial class Form1 : Form

{

int n = 1;

float[,] a, a1;

ArrayListkoord = new ArrayList();

public Form1()

{

InitializeComponent();

}

private void control()

{

a = new float[n, n];

a1 = new float[n, n];

bool flag = true;

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

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

try

{

a[i, j] = Convert.ToSingle(dataGridView1[j, i].Value);

}

catch

{

a[i, j] = 0;

flag = false;

}

if (flag == false)

{

MessageBox.Show("Введенное вами значение имеет некорректный формат", "Ошибкa");

return;

}

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

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

a1[i, j] = Convert.ToSingle(dataGridView2[j, i].Value);

}

private void numericUpDown1_ValueChanged(object sender, EventArgs e)

{

n = (byte)numericUpDown1.Value;

dataGridView1.ColumnCount = n;

dataGridView1.RowCount = n;

dataGridView2.ColumnCount = n;

dataGridView2.RowCount = n;

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

{

dataGridView1[i, i].Style.BackColor = Color.Gray;

dataGridView1[i, i].Value = 0;

dataGridView1[i, i].ReadOnly = true;

dataGridView2[i, i].Style.BackColor = Color.Gray;

dataGridView2[i, i].Value = 0;

dataGridView2[i, i].ReadOnly = true;

}

private void Form1_Load(object sender, EventArgs e)

{

numericUpDown1_ValueChanged(sender, e);

button1.Enabled = false;

построитьToolStripMenuItem.Enabled = false;

button2.Enabled = false;

progressBar1.Hide();

}

private void button2_Click(object sender, EventArgs e)

{

progressBar1.Show();

progressBar1.Maximum = n * n;

progressBar1.Value = 0;

Random x = new Random();

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

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

{

progressBar1.Value++;

if (i != j)

{

dataGridView1[i, j].Value = x.Next(0, 20);

}

progressBar1.Value = progressBar1.Maximum;

progressBar1.Value = progressBar1.Minimum;

progressBar1.Hide();

}

private void button3_Click(object sender, EventArgs e)

{

if (MessageBox.Show("Выдействительнохотитесброситьстарыерезультаты?", "Подтверждениевыбора", MessageBoxButtons.YesNo) == DialogResult.Yes)

{

progressBar1.Show();

progressBar1.Value = 0;

progressBar1.Maximum = 2 * n * n;

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

{

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

{

progressBar1.Value++;

if (i != j)

{

dataGridView1[i, j].Value = null;

dataGridView2[i, j].Value = null;

a[i, j] = 0;

a1[i, j] = 0;

}

koord.Clear();

n = 1;

numericUpDown1.Value = n;

pictureBox1.Invalidate();

pictureBox2.Invalidate();

progressBar1.Value = 0;

button1.Enabled = false;

progressBar1.Value = progressBar1.Maximum;

progressBar1.Hide();

}

private void dataGridView1_CellBeginEdit(object sender, DataGridViewCellCancelEventArgs e)

{

if (e.ColumnIndex == e.RowIndex)

e.Cancel = true;

}

private void dataGridView1_CellValueChanged(object sender, DataGridViewCellEventArgs e)

{

bool flag1 = true;

button1.Enabled = true;

try

{

Convert.ToDouble(dataGridView1[e.ColumnIndex, e.RowIndex].Value);

dataGridView1[e.ColumnIndex, e.RowIndex].Style.ForeColor = Color.Black;

}

catch

{

dataGridView1[e.ColumnIndex, e.RowIndex].Style.ForeColor = Color.Red;

toolStripStatusLabel1.Text = "Ошибкавкраснойячейке (" + (e.RowIndex + 1) + "," + (e.ColumnIndex + 1) + ")";

flag1 = false;

}

if (flag1)

dataGridView1[e.RowIndex, e.ColumnIndex].Value = dataGridView1[e.ColumnIndex, e.RowIndex].Value;

построитьToolStripMenuItem.Enabled = true;

pictureBox1.Invalidate();

}

private void button1_Click(object sender, EventArgs e)

{

progressBar1.Show();

progressBar1.Value = 0;

if (n <= 2)

progressBar1.Maximum = 16;

else

progressBar1.Maximum = n*n*n*n/2;

control();

a1 = newfloat[n, n]; //Матрица весов окончательной матрицы

short[,] b = newshort[n, n]; //Массив компонент (двумерный)

float[] c; //Массив ребер (вещественный)

progressBar1.Value++;

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

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

b[i, j] = -1;

progressBar1.Value++;

//Заполнение массива компонент (первая строка)

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

b[0, i] = i;

progressBar1.Value++;

short re = 0;

//Проверкачисларебер

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

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

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

re++;

c = new float[re];

re = 0;

progressBar1.Value++;

//Добавление ребер в массив ребер

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

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

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

{

c[re] = a[i, j];

re++;

}

progressBar1.Value++;

//Упорядочение массива ребер по возрастанию

float g; //Обменник (вещественная переменная)

short l;

while(true)

{

l = 0;

for(short i = 1; i< re; i++)

{

if(c[i] < c[i - 1])

{

g = c[i - 1];

c[i - 1] = c[i];

c[i] = g;

l++;

}

if(l == 0)

break;

}

progressBar1.Value++;

//Выполнениеалгоритма

short com1 = 0, com2 = 0, n3;

bool flag = false;

for(short k = 0; k < re; k++)

{ //Поискребравматрицевесов

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

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

{

progressBar1.Value++;

if (c[k] == a[i, j] && c[k] != a1[i, j])

{

//Проверка вершин на принадлежность разным компонентам

flag = false;

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

{

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

if (i == b[n1, n2])

{

com1 = n2;

flag = true;

}

if (flag)

break;

}

flag = false;

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

{

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

if (j == b[n1, n2])

{

com2 = n2;

flag = true;

}

if (flag)

break;

}

if (com1 != com2)

{ //Добавление ребра в остовый лес

a1[i, j] = c[k];

a1[j, i] = c[k];

//Обьединение двух соединенных компонент в одну

n3 = 0;

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

if (b[t, com1] == -1)

{

while (b[n3, com2] != -1)

{

b[n3 + t, com1] = b[n3, com2];

b[n3, com2] = -1;

n3++;

}

break;

}

//Изъятие использованного ребра из массива ребер

c[k] = 0;

}

progressBar1.Value++;

//На выходе получаем матрицу остовного леса

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

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

{

dataGridView2[i, j].Value = a1[i, j];

dataGridView2[j, i].Value = a1[i, j];

}

progressBar1.Value++;

progressBar1.Value = progressBar1.Maximum;

progressBar1.Value = progressBar1.Minimum;

progressBar1.Hide();

pictureBox2.Invalidate();

}

private void выходToolStripMenuItem_Click(object sender, EventArgs e)

{

Application.Exit();

}

private void построитьToolStripMenuItem_Click(object sender, EventArgs e)

{

button1_Click(sender, e);

}

private void слЧислаToolStripMenuItem_Click(object sender, EventArgs e)

{

button2_Click(sender, e);

}

private void сбросToolStripMenuItem_Click(object sender, EventArgs e)

{

button3_Click(sender, e);

}

private void сохранитьГрафToolStripMenuItem_Click(object sender, EventArgs e)

{

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

int[] x = new int[pnt.Length];

int[] y = new int[pnt.Length];

for (inti = 0; i<pnt.Length; i++)

{

x[i] = pnt[i].X;

y[i] = pnt[i].Y;

}

progressBar1.Maximum = 2 * n * n;

progressBar1.Value = 0;

control();

SaveFileDialog s = new SaveFileDialog();

s.DefaultExt = ".xml";

s.Filter = "Графвформате *.xml|*.xml";

if (s.ShowDialog() != DialogResult.OK) return;

XmlTextWriter w = new XmlTextWriter(s.FileName, null);

w.Formatting = Formatting.Indented;

w.WriteStartDocument();

w.WriteStartElement ("Структура");

w.WriteStartElement ("Неориентированный_граф");

w.WriteAttributeString( "Вершин", XmlConvert.ToString(n));

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

{

w.WriteStartElement("Строка_" + (i + 1));

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

{

progressBar1.Value++;

w.WriteAttributeString("Яч_" + (j + 1), XmlConvert.ToString(a[i, j]));

}

w.WriteEndElement();

}

w.WriteEndElement();

w.WriteStartElement ("Остовый_лес");

w.WriteAttributeString ("Вершин", XmlConvert.ToString(n));

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

{

w.WriteStartElement ("Строка_" + (i + 1));

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

{

progressBar1.Value++;

w.WriteAttributeString("Яч_" + (j + 1), XmlConvert.ToString(a1[i, j]));

}

w.WriteEndElement();

}

w.WriteEndElement();

w.WriteStartElement ("Массив_координат");

w.WriteAttributeString ("Вершин", XmlConvert.ToString(n));

w.WriteStartElement ("Координаты_x");

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

w.WriteAttributeString ("В_" + (i + 1), x[i].ToString());

w.WriteEndElement();

w.WriteStartElement("Координаты_y");

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

w.WriteAttributeString("В_" + (i + 1), y[i].ToString());

w.WriteEndElement();

w.WriteEndDocument();

w.Close();

progressBar1.Value = progressBar1.Maximum;

progressBar1.Value = progressBar1.Minimum;

progressBar1.Hide();

}

private void загрузитьГрафToolStripMenuItem_Click(object sender, EventArgs e)

{

button3_Click(sender, e);

int[] x, y;

Point pnt = new Point();

OpenFileDialog o = new OpenFileDialog();

o.DefaultExt = ".xml";

o.Filter = "Графвформате *.xml|*.xml";

if (o.ShowDialog() != DialogResult.OK) return;

XmlTextReader r = new XmlTextReader(o.FileName);

while (r.Read() && (r.Name != "Структура"));

while (r.Read() && (r.Name != "Неориентированный_граф"));

numericUpDown1.Value = XmlConvert.ToInt32(r.GetAttribute("Вершин"));

n = (int)numericUpDown1.Value;

x = new int[n];

y = new int[n];

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

{

while (r.Read() && (r.Name != "Строка_" + (i + 1))) ;

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

{

dataGridView1[j, i].Value = XmlConvert.ToDouble(r.GetAttribute("Яч_" + (j + 1)));

}

while (r.Read() && (r.Name != "Остовый_лес")) ;

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

{

while (r.Read() && (r.Name != "Строка_" + (i + 1))) ;

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

{

dataGridView2[j, i].Value = XmlConvert.ToDouble(r.GetAttribute("Яч_" + (j + 1)));

}

while (r.Read() && (r.Name != "Массив_координат")) ;

while (r.Read() && (r.Name != "Координаты_x")) ;

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

{

x[i] = XmlConvert.ToInt32(r.GetAttribute("В_" + (i + 1)));

}

while (r.Read() && (r.Name != "Координаты_y")) ;

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

{

y[i] = XmlConvert.ToInt32(r.GetAttribute("В_" + (i + 1)));

}

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

{

pnt.X = x[i];

pnt.Y = y[i];

koord.Add(pnt);

}

pictureBox1.Invalidate();

pictureBox2.Invalidate();

}

private void button4_Click(object sender, EventArgs e)

{

koord.Clear();

Random z1 = new Random();

Point x = new Point();

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

{

x.X = z1.Next(20, pictureBox1.ClientSize.Width - 20);

x.Y = z1.Next(20, pictureBox1.ClientSize.Height - 20);

koord.Add(x);

}

pictureBox1.Invalidate();

}

private void справкаToolStripMenuItem_Click(object sender, EventArgs e)

{

}

public void pictureBox1_Paint(object sender, PaintEventArgs e)

{

if (koord.Count != n)

return;

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

Алгоритм краскала 📙 Курсовая → 🆔 6328