Главная страница
qrcode

Лабораторная работ - Прикладная Информатика. Отчет по лаборатонкой работе по курсу Прикладная Информатика


Скачать 474.06 Kb.
НазваниеОтчет по лаборатонкой работе по курсу Прикладная Информатика
АнкорЛабораторная работ - Прикладная Информатика.docx
Дата10.09.2019
Размер474.06 Kb.
Формат файлаdocx
Имя файлаЛабораторная работ - Прикладная Информатика.docx
ТипОтчет
#58438
Каталог

Министерство образования и науки Российской Федерации

федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Самарский государственный аэрокосмический

Университет имени академика С.П. Королева

(Национальный исследовательский университет) »
Кафедра электроные системы и устройства
Отчет по лаборатонкой работе по курсу «Прикладная Информатика»

«Алгоритм Краскала»

Выполнил: студент гр. 545

Никитин А.А.

Проверил: Лофицкий И.В.

Самара 2011

Цель работы – познакомиться с приемами составления математической модели конкретной технической задачи, методами алгоритмизации и оптимизации технических решений при автоматизированном конструкторском и технологическом проектировании РЭА.

Задание
Техническая задача: провести трассировку локальной сети имеющей топологию дерево по алгоритму Краскала. Основной критерий - Минимальная протяженность сети. С учетом начальных данных: координаты коммутирующих устройств и наличие связей между ними.

Содержание
Введение..…………………………………………………..…….…4

Алгоритм программы………..……………………..…...….……..15

Листинг программы………………………..……………………..16

Контрольный пример…………………........……..……..…..……26

Заключение……………………………………….………...……..31

Список используемых источников..…………….…………..…...32

Введение Алгоритм Краскала

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

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

Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

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

Удобно использовать для хранения компонент структуры данных для непересекающихся множеств, как, например, списки или, что лучше, лес непересекающихся множеств со сжатием путей и объединением по рангу (один из самых быстрых известных методов). Элементами множеств являются вершины графа, каждое множество содержит вершины одной связной компоненты. Для работы с множествами используются следующие процедуры2
Make-Set(v)
Создание множества из набора вершин
Find-Set(v)
Возвращает множество, содержащее данную вершину
Union(u,v)
Объединяет множества, содержащие данные вершины

Общая схема алгоритма выглядит так3
MST-KRUSKAL(G,w)
1: A ← 0
2: foreach (для каждой) вершины 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:         AA присваиваем {(u,v)}
8:         Union(u,v)
9: returnA

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

Рис. 1 Начальная фаза. Минимальный покрывающий лес пуст.

Рис. 2 Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.

Рис. 3 Следующее безопасное ребро с весом 6. Добавляем его.

Рис. 4.

Рис. 5

Рис. 6

Рис. 7

Рис. 8 Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Описание программы

Рис. 9 Диалоговое окно

Диалоговое окно можно разбить на несколько элементов:
Блок ввода информации:
- PictureBox «Расположение» для ввода координат.

- Набор TextBox-ов «Координаты» для точного отображения координат

- Набор CheckBox-ов «Матрица связности» для ввода связности
    Блок вывода информации:
    - PictureBox «Итоговые связи» для вывода конечного результата
      Блок отображения текущей информации:
      - TextBox отображающий количество вершин графа (количеств коммутирующих устройств)

      - TextBox-ы «Текущие координаты» для отображения текущего положения курсора на PictureBox «Расположение»
        Блок кнопок:
        - кнопка «Построить все связи» - в матрице связности просчитываются все возможные связи между вершинами графа(подпрограмма №1), после чего, на PictureBox «Расположение» строятся все возможные связи

        - кнопка «Построить по координатам» - рисует на PictureBox«Расположение» координаты из набора TextBox «Координаты»

        - кнопка «Все вершины связаны» - заполняет матрицу связности с условием что все вершины графа связаны

        - кнопка «Расчет кратчайших связей» - выполнение основного алгоритма (подпрограмма №2), отображение на PictureBox «Итоговые связи» конечный граф.

        - кнопка «Очистить» - очищает все поля программы

        - кнопка «Выход» - выход из программы
        Алгоритмы программы
        Описание алгоритма

        Ввод координат может осуществляться двумя способами через TextBox (ввод числовых значений координат), или рисование точек на PictureBox (программа сама определяет координаты и заносит их в TextBox).

        Ввод матрицы связности осуществляется через массив CheckBox-ов. Ссвязь между вершинами определяется по значению CheckBox-а (true – связь есть, false – связи нет). После проставления вершин, которые необходимо соединить, программа сама проверит матрицу связности и проставит все варианты связей, которые могут быть при донной связанности.

        После нажатия кнопки «Расчет кратчайших связей» программа выполняет «Подпрограмму №2», результатом которой будет являться двумерный массив связей ссылок на массив координат вершин.

        Дальнейшая работа программы будет заключаться в изображении связей полученных в результате вычисления «Подпрограммы №2».
        Подпрограмма №1

        Подпрограмма №2

        Листинг программы
        using System;

        using System.Collections.Generic;

        using System.ComponentModel;

        using System.Data;

        using System.Drawing;

        using System.Linq;

        using System.Text;

        using System.Windows.Forms;
        namespace WindowsFormsApplication1

        {

        public partial class Form1 : Form

        {

        public Form1()

        {

        InitializeComponent();

        GetGraphicsToPixtureBox();

        GetGraphicsToPixtureBox2();

        ZapolnenieKoord();
        }

        private Graphics g; // Объявляем пространство g

        private Graphics g2; // Объявляем пространство g2

        private void Form1_Load(object sender, EventArgs e)

        {
        }

        public void ZapolnenieKoord()

        {

        tbX1.Text = Convert.ToString(0);

        tbX2.Text = Convert.ToString(0);

        tbX3.Text = Convert.ToString(0);

        tbX4.Text = Convert.ToString(0);

        tbX5.Text = Convert.ToString(0);

        tbX6.Text = Convert.ToString(0);

        tbX7.Text = Convert.ToString(0);

        tbX8.Text = Convert.ToString(0);

        tbX9.Text = Convert.ToString(0);

        tbX10.Text = Convert.ToString(0);

        tbY1.Text = Convert.ToString(0);

        tbY2.Text = Convert.ToString(0);

        tbY3.Text = Convert.ToString(0);

        tbY4.Text = Convert.ToString(0);

        tbY5.Text = Convert.ToString(0);

        tbY6.Text = Convert.ToString(0);

        tbY7.Text = Convert.ToString(0);

        tbY8.Text = Convert.ToString(0);

        tbY9.Text = Convert.ToString(0);

        tbY10.Text = Convert.ToString(0);

        n = 0;
        }

        private void GetGraphicsToPixtureBox() // Описываем пространство g

        {

        pbPaint.Image = new Bitmap(pbPaint.Width, pbPaint.Height);

        g = Graphics.FromImage(pbPaint.Image);

        g.Clear(Color.White);


        }

        private void GetGraphicsToPixtureBox2() // Описываем пространство g2

        {

        pbItog.Image = new Bitmap(pbItog.Width, pbItog.Height);

        g2 = Graphics.FromImage(pbItog.Image);

        g2.Clear(Color.White);

        }

        Pen p = new Pen(Color.Black, 5); // Перо вершины

        Pen p2 = new Pen(Color.Green, 1); // Перо связи

        Pen p1 = new Pen(Color.Black, 6);

        Pen p21 = new Pen(Color.Green, 2);

        int n=0;

        int[,] koord = new int[20, 2]; // Массив координат

        public void pbPaint_MouseDown(object sender, MouseEventArgs e)

        {

        int x1;

        int y1;

        var font = new Font("Arial", 12);

        x1 = Convert.ToInt32(e.X);

        y1 = Convert.ToInt32(e.Y);

        g.DrawLine(p, x1, y1, x1 + 5, y1);

        pbPaint.Invalidate();

        koord[n, 0] = x1;

        koord[n, 1] = y1;

        ++n;

        tbN.Text = Convert.ToString(n);

        g.DrawString(Convert.ToString(n), font, Brushes.Black, new Point(x1 + 2, y1 + 2));

        pbPaint.Invalidate();

        switch(n)

        {

        case 1:

        tbX1.Text = Convert.ToString(x1);

        tbY1.Text = Convert.ToString(y1);

        break;

        case 2:

        tbX2.Text = Convert.ToString(x1);

        tbY2.Text = Convert.ToString(y1);

        break;

        case 3:

        tbX3.Text = Convert.ToString(x1);

        tbY3.Text = Convert.ToString(y1);

        break;

        case 4:

        tbX4.Text = Convert.ToString(x1);

        tbY4.Text = Convert.ToString(y1);

        break;

        case 5:

        tbX5.Text = Convert.ToString(x1);

        tbY5.Text = Convert.ToString(y1);

        break;

        case 6:

        tbX6.Text = Convert.ToString(x1);

        tbY6.Text = Convert.ToString(y1);

        break;

        case 7:

        tbX7.Text = Convert.ToString(x1);

        tbY7.Text = Convert.ToString(y1);

        break;

        case 8:

        tbX8.Text = Convert.ToString(x1);

        tbY8.Text = Convert.ToString(y1);

        break;

        case 9:

        tbX9.Text = Convert.ToString(x1);

        tbY9.Text = Convert.ToString(y1);

        break;

        case 10:

        tbX10.Text = Convert.ToString(x1);

        tbY10.Text = Convert.ToString(y1);

        break;
        }

        }

        bool[,] sviazi = new bool[20, 20];
        // Проверяем чекбоксы и проставляем необходимые

        private void btOpr_Click(object sender, EventArgs e)

        {
        int i;

        int j;

        int N;

        int t;

        int Temp;

        int iTemp;

        int jTemp;

        int[] ver = new int[20];

        N = Convert.ToInt32(tbN.Text);

        sviazi[0, 0] = false;

        sviazi[1, 0] = cb2_1.Checked;

        sviazi[2, 0] = cb3_1.Checked;

        sviazi[3, 0] = cb4_1.Checked;

        sviazi[4, 0] = cb5_1.Checked;

        sviazi[5, 0] = cb6_1.Checked;

        sviazi[6, 0] = cb7_1.Checked;

        sviazi[7, 0] = cb8_1.Checked;

        sviazi[8, 0] = cb9_1.Checked;

        sviazi[9, 0] = cb10_1.Checked;

        sviazi[0, 1] = cb1_2.Checked;

        sviazi[1, 1] = false;

        sviazi[2, 1] = cb3_2.Checked;

        sviazi[3, 1] = cb4_2.Checked;

        sviazi[4, 1] = cb5_2.Checked;

        sviazi[5, 1] = cb6_2.Checked;

        sviazi[6, 1] = cb7_2.Checked;

        sviazi[7, 1] = cb8_2.Checked;

        sviazi[8, 1] = cb9_2.Checked;

        sviazi[9, 1] = cb10_2.Checked;

        sviazi[0, 2] = cb1_3.Checked;

        sviazi[1, 2] = cb2_3.Checked;

        sviazi[2, 2] = false;

        sviazi[3, 2] = cb4_3.Checked;

        sviazi[4, 2] = cb5_3.Checked;

        sviazi[5, 2] = cb6_3.Checked;

        sviazi[6, 2] = cb7_3.Checked;

        sviazi[7, 2] = cb8_3.Checked;

        sviazi[8, 2] = cb9_3.Checked;

        sviazi[9, 2] = cb10_3.Checked;

        sviazi[0, 3] = cb1_4.Checked;

        sviazi[1, 3] = cb2_4.Checked;

        sviazi[2, 3] = cb3_4.Checked;

        sviazi[3, 3] = false;

        sviazi[4, 3] = cb5_4.Checked;

        sviazi[5, 3] = cb6_4.Checked;

        sviazi[6, 3] = cb7_4.Checked;

        sviazi[7, 3] = cb8_4.Checked;

        sviazi[8, 3] = cb9_4.Checked;

        sviazi[9, 3] = cb10_4.Checked;

        sviazi[0, 4] = cb1_5.Checked;

        sviazi[1, 4] = cb2_5.Checked;

        sviazi[2, 4] = cb3_5.Checked;

        sviazi[3, 4] = cb4_5.Checked;

        sviazi[4, 4] = false;

        sviazi[5, 4] = cb6_5.Checked;

        sviazi[6, 4] = cb7_5.Checked;

        sviazi[7, 4] = cb8_5.Checked;

        sviazi[8, 4] = cb9_5.Checked;

        sviazi[9, 4] = cb10_5.Checked;
        sviazi[0, 5] = cb1_6.Checked;

        sviazi[1, 5] = cb2_6.Checked;

        sviazi[2, 5] = cb3_6.Checked;

        sviazi[3, 5] = cb4_6.Checked;

        sviazi[4, 5] = cb5_6.Checked;

        sviazi[5, 5] = false;

        sviazi[6, 5] = cb7_6.Checked;

        sviazi[7, 5] = cb8_6.Checked;

        sviazi[8, 5] = cb9_6.Checked;

        sviazi[9, 5] = cb10_6.Checked;
        sviazi[0, 6] = cb1_7.Checked;

        sviazi[1, 6] = cb2_7.Checked;

        sviazi[2, 6] = cb3_7.Checked;

        sviazi[3, 6] = cb4_7.Checked;

        sviazi[4, 6] = cb5_7.Checked;

        sviazi[5, 6] = cb6_7.Checked;

        sviazi[6, 6] = false;

        sviazi[7, 6] = cb8_7.Checked;

        sviazi[8, 6] = cb9_7.Checked;

        sviazi[9, 6] = cb10_7.Checked;
        sviazi[0, 7] = cb1_8.Checked;

        sviazi[1, 7] = cb2_8.Checked;

        sviazi[2, 7] = cb3_8.Checked;

        sviazi[3, 7] = cb4_8.Checked;

        sviazi[4, 7] = cb5_8.Checked;

        sviazi[5, 7] = cb6_8.Checked;

        sviazi[6, 7] = cb7_8.Checked;

        sviazi[7, 7] = false;

        sviazi[8, 7] = cb9_8.Checked;

        sviazi[9, 7] = cb10_8.Checked;
        sviazi[0, 8] = cb1_9.Checked;

        sviazi[1, 8] = cb2_9.Checked;

        sviazi[2, 8] = cb3_9.Checked;

        sviazi[3, 8] = cb4_9.Checked;

        sviazi[4, 8] = cb5_9.Checked;

        sviazi[5, 8] = cb6_9.Checked;

        sviazi[6, 8] = cb7_9.Checked;

        sviazi[7, 8] = cb8_9.Checked;

        sviazi[8, 8] = false;

        sviazi[9, 8] = cb10_9.Checked;
        sviazi[0, 9] = cb1_10.Checked;

        sviazi[1, 9] = cb2_10.Checked;

        sviazi[2, 9] = cb3_10.Checked;

        sviazi[3, 9] = cb4_10.Checked;

        sviazi[4, 9] = cb5_10.Checked;

        sviazi[5, 9] = cb6_10.Checked;

        sviazi[6, 9] = cb7_10.Checked;

        sviazi[7, 9] = cb8_10.Checked;

        sviazi[8, 9] = cb9_10.Checked;

        sviazi[9, 9] = false;


        for (i = 0; i < N; ++i)

        {

        ver[i] = 0;

        }

        Temp = 0;

        for (i = 0; i < N; ++i) // Заполняем необходимые чекбоксы

        {

        for (j = 0; j < N; ++j)

        {

        if (sviazi[i, j] == true)

        {

        ++Temp;

        if (ver[i] == 0)

        {

        if (ver[j] == 0)

        {

        iTemp = ver[i];

        jTemp = ver[j];

        ver[i] = Temp;

        ver[j] = Temp;

        ++Temp;

        goto next;

        }

        }

        if (ver[i] == ver[j])

        {

        goto next;

        }

        iTemp = ver[i];

        jTemp = ver[j];

        ver[i] = Temp;

        ver[j] = Temp;

        for (t = 0; t < N; ++t)

        {

        if (ver[t] == iTemp)

        {

        if (iTemp > 0)

        {

        ver[t] = Temp;

        }
        }

        if (ver[t] == jTemp)

        {

        if (jTemp > 0)

        {

        ver[t] = Temp;

        }

        }

        }

        }

        next: continue;

        }

        }
        for (i = 0; i < N+1; ++i) // Заполнение массива связей

        {

        for (j = 0; j < N+1; ++j)

        {

        if (i == j)

        {

        sviazi[i,j]=false;

        }

        else

        {

        if (ver[i] == ver[j])

        {

        if (ver[i] != 0)

        {

        sviazi[i, j] = true;

        sviazi[j, i] = true;

        }

        else

        {

        sviazi[i, j] = false;

        sviazi[j, i] = false;

        }

        }

        else

        {

        sviazi[i, j] = false;

        sviazi[j, i] = false;

        }

        }

        }

        }

        // Итоговое заполнение массивов

        cb1_1.Checked = sviazi[0, 0];

        cb2_1.Checked = sviazi[1, 0];

        cb3_1.Checked = sviazi[2, 0];

        cb4_1.Checked = sviazi[3, 0];

        cb5_1.Checked = sviazi[4, 0];

        cb6_1.Checked = sviazi[5, 0];

        cb7_1.Checked = sviazi[6, 0];

        cb8_1.Checked = sviazi[7, 0];

        cb9_1.Checked = sviazi[8, 0];

        cb10_1.Checked = sviazi[9, 0];
        cb1_2.Checked = sviazi[0, 1];

        cb2_2.Checked = sviazi[1, 1];

        cb3_2.Checked = sviazi[2, 1];

        cb4_2.Checked = sviazi[3, 1];

        cb5_2.Checked = sviazi[4, 1];

        cb6_2.Checked = sviazi[5, 1];

        cb7_2.Checked = sviazi[6, 1];

        cb8_2.Checked = sviazi[7, 1];

        cb9_2.Checked = sviazi[8, 1];

        cb10_2.Checked = sviazi[9, 1];
        cb1_3.Checked = sviazi[0, 2];

        cb2_3.Checked = sviazi[1, 2];

        cb3_3.Checked = sviazi[2, 2];

        cb4_3.Checked = sviazi[3, 2];

        cb5_3.Checked = sviazi[4, 2];

        cb6_3.Checked = sviazi[5, 2];

        cb7_3.Checked = sviazi[6, 2];

        cb8_3.Checked = sviazi[7, 2];

        cb9_3.Checked = sviazi[8, 2];

        cb10_3.Checked = sviazi[9, 2];
        cb1_4.Checked = sviazi[0, 3];

        cb2_4.Checked = sviazi[1, 3];

        cb3_4.Checked = sviazi[2, 3];

        cb4_4.Checked = sviazi[3, 3];

        cb5_4.Checked = sviazi[4, 3];

        cb6_4.Checked = sviazi[5, 3];

        cb7_4.Checked = sviazi[6, 3];

        cb8_4.Checked = sviazi[7, 3];

        cb9_4.Checked = sviazi[8, 3];

        cb10_4.Checked = sviazi[9, 3];
        cb1_5.Checked = sviazi[0, 4];

        cb2_5.Checked = sviazi[1, 4];

        cb3_5.Checked = sviazi[2, 4];

        cb4_5.Checked = sviazi[3, 4];

        cb5_5.Checked = sviazi[4, 4];

        cb6_5.Checked = sviazi[5, 4];

        cb7_5.Checked = sviazi[6, 4];

        cb8_5.Checked = sviazi[7, 4];

        cb9_5.Checked = sviazi[8, 4];

        cb10_5.Checked = sviazi[9, 4];
        cb1_6.Checked = sviazi[0, 5];

        cb2_6.Checked = sviazi[1, 5];

        cb3_6.Checked = sviazi[2, 5];

        cb4_6.Checked = sviazi[3, 5];

        cb5_6.Checked = sviazi[4, 5];

        cb6_6.Checked = sviazi[5, 5];

        cb7_6.Checked = sviazi[6, 5];

        cb8_6.Checked = sviazi[7, 5];

        cb9_6.Checked = sviazi[8, 5];

        cb10_6.Checked = sviazi[9, 5];
        cb1_7.Checked = sviazi[0, 6];

        cb2_7.Checked = sviazi[1, 6];

        cb3_7.Checked = sviazi[2, 6];

        cb4_7.Checked = sviazi[3, 6];

        cb5_7.Checked = sviazi[4, 6];

        cb6_7.Checked = sviazi[5, 6];

        cb7_7.Checked = sviazi[6, 6];

        cb8_7.Checked = sviazi[7, 6];

        cb9_7.Checked = sviazi[8, 6];

        cb10_7.Checked = sviazi[9, 6];
        cb1_8.Checked = sviazi[0, 7];

        cb2_8.Checked = sviazi[1, 7];

        cb3_8.Checked = sviazi[2, 7];

        cb4_8.Checked = sviazi[3, 7];

        cb5_8.Checked = sviazi[4, 7];

        cb6_8.Checked = sviazi[5, 7];

        cb7_8.Checked = sviazi[6, 7];

        cb8_8.Checked = sviazi[7, 7];

        cb9_8.Checked = sviazi[8, 7];

        cb10_8.Checked = sviazi[9, 7];
        cb1_9.Checked = sviazi[0, 8];

        cb2_9.Checked = sviazi[1, 8];

        cb3_9.Checked = sviazi[2, 8];

        cb4_9.Checked = sviazi[3, 8];

        cb5_9.Checked = sviazi[4, 8];

        cb6_9.Checked = sviazi[5, 8];

        cb7_9.Checked = sviazi[6, 8];

        cb8_9.Checked = sviazi[7, 8];

        cb9_9.Checked = sviazi[8, 8];

        cb10_9.Checked = sviazi[9, 8];
        cb1_10.Checked = sviazi[0, 9];

        cb2_10.Checked = sviazi[1, 9];

        cb3_10.Checked = sviazi[2, 9];

        cb4_10.Checked = sviazi[3, 9];

        cb5_10.Checked = sviazi[4, 9];

        cb6_10.Checked = sviazi[5, 9];

        cb7_10.Checked = sviazi[6, 9];

        cb8_10.Checked = sviazi[7, 9];

        cb9_10.Checked = sviazi[8, 9];

        cb10_10.Checked = sviazi[9, 9];


        for (i = 1; i < N; ++i)

        {

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

        {

        if (sviazi[i, j] == true)

        {

        g.DrawLine(p2, koord[i, 0], koord[i, 1], koord[j, 0], koord[j, 1]);

        pbPaint.Invalidate();

        }

        }

        }

        }
        private void btClose_Click(object sender, EventArgs e)

        {

        this.Close();

        }

        // Обнуляем все поля

        private void btnClear_Click(object sender, EventArgs e)

        {

        cb1_1.Checked = false;

        cb2_1.Checked = false;

        cb3_1.Checked = false;

        cb4_1.Checked = false;

        cb5_1.Checked = false;

        cb6_1.Checked = false;

        cb7_1.Checked = false;

        cb8_1.Checked = false;

        cb9_1.Checked = false;

        cb10_1.Checked = false;
        cb1_2.Checked = false;

        cb2_2.Checked = false;

        cb3_2.Checked = false;

        cb4_2.Checked = false;

        cb5_2.Checked = false;

        cb6_2.Checked = false;

        cb7_2.Checked = false;

        cb8_2.Checked = false;

        cb9_2.Checked = false;

        cb10_2.Checked = false;
        cb1_3.Checked = false;

        cb2_3.Checked = false;

        cb3_3.Checked = false;

        cb4_3.Checked = false;

        cb5_3.Checked = false;

        cb6_3.Checked = false;

        cb7_3.Checked = false;

        cb8_3.Checked = false;

        cb9_3.Checked = false;

        cb10_3.Checked = false;
        cb1_4.Checked = false;

        cb2_4.Checked = false;

        cb3_4.Checked = false;

        cb4_4.Checked = false;

        cb5_4.Checked = false;

        cb6_4.Checked = false;

        cb7_4.Checked = false;

        cb8_4.Checked = false;

        cb9_4.Checked = false;

        cb10_4.Checked = false;
        cb1_5.Checked = false;

        cb2_5.Checked = false;

        cb3_5.Checked = false;

        cb4_5.Checked = false;

        cb5_5.Checked = false;

        cb6_5.Checked = false;

        cb7_5.Checked = false;

        cb8_5.Checked = false;

        cb9_5.Checked = false;

        cb10_5.Checked = false;
        cb1_6.Checked = false;

        cb2_6.Checked = false;

        cb3_6.Checked = false;

        cb4_6.Checked = false;

        cb5_6.Checked = false;

        cb6_6.Checked = false;

        cb7_6.Checked = false;

        cb8_6.Checked = false;

        cb9_6.Checked = false;

        cb10_6.Checked = false;
        cb1_7.Checked = false;

        cb2_7.Checked = false;

        cb3_7.Checked = false;

        cb4_7.Checked = false;

        cb5_7.Checked = false;

        cb6_7.Checked = false;

        cb7_7.Checked = false;

        cb8_7.Checked = false;

        cb9_7.Checked = false;

        cb10_7.Checked = false;
        cb1_8.Checked = false;

        cb2_8.Checked = false;

        cb3_8.Checked = false;

        cb4_8.Checked = false;

        cb5_8.Checked = false;

        cb6_8.Checked = false;

        cb7_8.Checked = false;

        cb8_8.Checked = false;

        cb9_8.Checked = false;

        cb10_8.Checked = false;
        cb1_9.Checked = false;

        cb2_9.Checked = false;

        cb3_9.Checked = false;

        cb4_9.Checked = false;

        cb5_9.Checked = false;

        cb6_9.Checked = false;

        cb7_9.Checked = false;

        cb8_9.Checked = false;

        cb9_9.Checked = false;

        cb10_9.Checked = false;
        cb1_10.Checked = false;

        cb2_10.Checked = false;

        cb3_10.Checked = false;

        cb4_10.Checked = false;

        cb5_10.Checked = false;

        cb6_10.Checked = false;

        cb7_10.Checked = false;

        cb8_10.Checked = false;

        cb9_10.Checked = false;

        cb10_10.Checked = false;
        tbX1.Text = Convert.ToString(0);

        tbX2.Text = Convert.ToString(0);

        tbX3.Text = Convert.ToString(0);

        tbX4.Text = Convert.ToString(0);

        tbX5.Text = Convert.ToString(0);

        tbX6.Text = Convert.ToString(0);

        tbX7.Text = Convert.ToString(0);

        tbX8.Text = Convert.ToString(0);

        tbX9.Text = Convert.ToString(0);

        tbX10.Text = Convert.ToString(0);

        tbY1.Text = Convert.ToString(0);

        tbY2.Text = Convert.ToString(0);

        tbY3.Text = Convert.ToString(0);

        tbY4.Text = Convert.ToString(0);

        tbY5.Text = Convert.ToString(0);

        tbY6.Text = Convert.ToString(0);

        tbY7.Text = Convert.ToString(0);

        tbY8.Text = Convert.ToString(0);

        tbY9.Text = Convert.ToString(0);

        tbY10.Text = Convert.ToString(0);
        n = 0;

        tbN.Text = Convert.ToString(n);
        g.Clear(Color.White);

        pbPaint.Invalidate();

        g2.Clear(Color.White);

        pbItog.Invalidate();

        }

        // Итоговый расчет кратчайшего расстояния

        Double[,] massiv = new Double[20, 20];

        int N;

        int Ns;

        int[,] save = new int[20, 2];

        private void btnItog_Click(object sender, EventArgs e)

        {

        int s;

        int vert = 0;

        int vert1;

        int vert2;

        int t;

        Double korTemp;

        int iTemp;

        int jTemp;

        int i;

        int j;

        int kKortej = 0;

        Double[] kortej = new Double[150];

        int[,] kortej2 = new int[150, 2];

        int[] ver = new int[20];

        var font = new Font("Arial", 16);
        N = Convert.ToInt32(tbN.Text);

        for (j = 0; j < N; ++j) // Строим вершины в g2

        {

        g2.DrawLine(p1, koord[j, 0]*2, koord[j, 1]*2, koord[j, 0]*2 + 6, koord[j, 1]*2 );

        pbItog.Invalidate();

        g2.DrawString(Convert.ToString(j + 1), font, Brushes.Black, new Point(koord[j, 0]*2 + 4, koord[j, 1]*2 + 4));

        pbItog.Invalidate();

        }
        for (i = 1; i < N; ++i)

        {

        massiv[i, i] = 0;

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

        {

        massiv[i, j] = Math.Round((Math.Sqrt(Math.Pow((koord[j, 0] - koord[i, 0]), 2) + Math.Pow((koord[j, 1] - koord[i, 1]), 2))), 1);

        massiv[j, i] = massiv[i, j];

        }

        }

        for (i = 1; i < N; ++i)

        {

        massiv[i, i] = 0;

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

        {

        kortej[kKortej] = massiv[i, j];

        kortej2[kKortej, 0] = i;

        kortej2[kKortej, 1] = j;

        ++kKortej;

        }

        }

        s = kKortej;
        for (t = 0; t < s + 1; ++t)

        {

        for (kKortej = 0; kKortej < s - 1; ++kKortej)

        {

        if (kortej[kKortej] > kortej[kKortej + 1])

        {

        korTemp = kortej[kKortej];

        iTemp = kortej2[kKortej, 0];

        jTemp = kortej2[kKortej, 1];

        kortej[kKortej] = kortej[kKortej + 1];

        kortej2[kKortej, 0] = kortej2[kKortej + 1, 0];

        kortej2[kKortej, 1] = kortej2[kKortej + 1, 1];

        kortej[kKortej + 1] = korTemp;

        kortej2[kKortej + 1, 0] = iTemp;

        kortej2[kKortej + 1, 1] = jTemp;

        }

        }

        }

        Ns = 0;

        for (kKortej = 0; kKortej < s; ++kKortej)

        {

        if (sviazi[kortej2[kKortej, 0], kortej2[kKortej, 1]] == true)

        {

        ++vert;

        if (ver[kortej2[kKortej, 0]] == 0)

        {

        if (ver[kortej2[kKortej, 1]] == 0)

        {

        ver[kortej2[kKortej, 0]] = vert;

        ver[kortej2[kKortej, 1]] = vert;

        save[Ns, 0] = kortej2[kKortej, 0];

        save[Ns, 1] = kortej2[kKortej, 1];

        ++Ns;

        goto next;

        }

        }

        if (ver[kortej2[kKortej, 0]] == ver[kortej2[kKortej, 1]])

        {

        goto next;

        }

        vert1 = ver[kortej2[kKortej, 0]];

        vert2 = ver[kortej2[kKortej, 1]];

        ver[kortej2[kKortej, 0]] = vert;

        ver[kortej2[kKortej, 1]] = vert;

        for (i = 0; i < N; ++i)

        {

        if (ver[i] == vert1)

        {

        if (vert1 > 0)

        {

        ver[i] = vert;

        }
        }

        if (ver[i] == vert2)

        {

        if (vert2 > 0)

        {

        ver[i] = vert;

        }
        }

        }

        save[Ns, 0] = kortej2[kKortej, 0];

        save[Ns, 1] = kortej2[kKortej, 1];

        ++Ns;

        }
        next: continue;

        }
        // Рисуем связи

        for (i = 0; i < Ns; ++i)

        {

        g2.DrawLine(p21, koord[save[i, 0], 0]*2, koord[save[i, 0], 1]*2, koord[save[i, 1], 0]*2, koord[save[i, 1], 1]*2);

        pbItog.Invalidate();

        }

        }
        private void pbPaint_MouseMove(object sender, MouseEventArgs e)

        {

        int xTime;

        int yTime;

        xTime = Convert.ToInt32(e.X);

        yTime = Convert.ToInt32(e.Y);

        tbX.Text = Convert.ToString(xTime);

        tbY.Text = Convert.ToString(yTime);

        }
        private void pbPaint_MouseLeave(object sender, EventArgs e)

        {

        tbX.Clear();

        tbY.Clear();

        }
        private void btnRasKoord_Click(object sender, EventArgs e)

        {

        int i;

        int j;

        var font = new Font("Arial", 12);

        int[,] koordTemp=new int[20,2];

        for (i = n; i < 11; ++i)

        {

        switch (i)

        {

        case 0:

        koord[i, 0] = Convert.ToInt32(tbX1.Text);

        koord[i, 1] = Convert.ToInt32(tbY1.Text);

        break;

        case 1:

        koord[i, 0] = Convert.ToInt32(tbX2.Text);

        koord[i, 1] = Convert.ToInt32(tbY2.Text);

        break;

        case 2:

        koord[i, 0] = Convert.ToInt32(tbX3.Text);

        koord[i, 1] = Convert.ToInt32(tbY3.Text);

        break;

        case 3:

        koord[i, 0] = Convert.ToInt32(tbX4.Text);

        koord[i, 1] = Convert.ToInt32(tbY4.Text);

        break;

        case 4:

        koord[i, 0] = Convert.ToInt32(tbX5.Text);

        koord[i, 1] = Convert.ToInt32(tbY5.Text);

        break;

        case 5:

        koord[i, 0] = Convert.ToInt32(tbX6.Text);

        koord[i, 1] = Convert.ToInt32(tbY6.Text);

        break;

        case 6:

        koord[i, 0] = Convert.ToInt32(tbX7.Text);

        koord[i, 1] = Convert.ToInt32(tbY7.Text);

        break;

        case 7:

        koord[i, 0] = Convert.ToInt32(tbX8.Text);

        koord[i, 1] = Convert.ToInt32(tbY8.Text);

        break;

        case 8:

        koord[i, 0] = Convert.ToInt32(tbX9.Text);

        koord[i, 1] = Convert.ToInt32(tbY9.Text);

        break;

        case 9:

        koord[i, 0] = Convert.ToInt32(tbX10.Text);

        koord[i, 1] = Convert.ToInt32(tbY10.Text);

        break;
        }

        }

        j = 0;

        for (i = n; i < 11; ++i)

        {

        if (koord[i, 0] == 0)

        {

        if (koord[i, 1] == 0)

        {

        if (j == 0)

        {

        j = i;
        }

        }

        }

        }

        for (i = n; i < j; ++i)

        {

        g.DrawLine(p, koord[i, 0], koord[i, 1], koord[i, 0] + 5, koord[i, 1]);

        pbPaint.Invalidate();
        tbN.Text = Convert.ToString(n);

        g.DrawString(Convert.ToString(i+1), font, Brushes.Black, new Point(koord[i,0] + 2, koord[i,1] + 2));

        pbPaint.Invalidate();

        n = j;

        tbN.Text = Convert.ToString(n);

        }

        }
        private void button1_Click(object sender, EventArgs e)

        {

        cb1_1.Checked = false;

        cb2_1.Checked = true;

        cb3_1.Checked = true;

        cb4_1.Checked = true;

        cb5_1.Checked = true;

        cb6_1.Checked = true;

        cb7_1.Checked = true;

        cb8_1.Checked = true;

        cb9_1.Checked = true;

        cb10_1.Checked = true;
        cb1_2.Checked = true;

        cb2_2.Checked = false;

        cb3_2.Checked = true;

        cb4_2.Checked = true;

        cb5_2.Checked = true;

        cb6_2.Checked = true;

        cb7_2.Checked = true;

        cb8_2.Checked = true;

        cb9_2.Checked = true;

        cb10_2.Checked = true;
        cb1_3.Checked = true;

        cb2_3.Checked = true;

        cb3_3.Checked = false;

        cb4_3.Checked = true;

        cb5_3.Checked = true;

        cb6_3.Checked = true;

        cb7_3.Checked = true;

        cb8_3.Checked = true;

        cb9_3.Checked = true;

        cb10_3.Checked = true;
        cb1_4.Checked = true;

        cb2_4.Checked = true;

        cb3_4.Checked = true;

        cb4_4.Checked = false;

        cb5_4.Checked = true;

        cb6_4.Checked = true;

        cb7_4.Checked = true;

        cb8_4.Checked = true;

        cb9_4.Checked = true;

        cb10_4.Checked = true;
        cb1_5.Checked = true;

        cb2_5.Checked = true;

        cb3_5.Checked = true;

        cb4_5.Checked = true;

        cb5_5.Checked = false;

        cb6_5.Checked = true;

        cb7_5.Checked = true;

        cb8_5.Checked = true;

        cb9_5.Checked = true;

        cb10_5.Checked = true;
        cb1_6.Checked = true;

        cb2_6.Checked = true;

        cb3_6.Checked = true;

        cb4_6.Checked = true;

        cb5_6.Checked = true;

        cb6_6.Checked = false;

        cb7_6.Checked = true;

        cb8_6.Checked = true;

        cb9_6.Checked = true;

        cb10_6.Checked = true;
        cb1_7.Checked = true;

        cb2_7.Checked = true;

        cb3_7.Checked = true;

        cb4_7.Checked = true;

        cb5_7.Checked = true;

        cb6_7.Checked = true;

        cb7_7.Checked = false;

        cb8_7.Checked = true;

        cb9_7.Checked = true;

        cb10_7.Checked = true;
        cb1_8.Checked = true;

        cb2_8.Checked = true;

        cb3_8.Checked = true;

        cb4_8.Checked = true;

        cb5_8.Checked = true;

        cb6_8.Checked = true;

        cb7_8.Checked = true;

        cb8_8.Checked = false;

        cb9_8.Checked = true;

        cb10_8.Checked = true;
        cb1_9.Checked = true;

        cb2_9.Checked = true;

        cb3_9.Checked = true;

        cb4_9.Checked = true;

        cb5_9.Checked = true;

        cb6_9.Checked = true;

        cb7_9.Checked = true;

        cb8_9.Checked = true;

        cb9_9.Checked = false;

        cb10_9.Checked = true;
        cb1_10.Checked = true;

        cb2_10.Checked = true;

        cb3_10.Checked = true;

        cb4_10.Checked = true;

        cb5_10.Checked = true;

        cb6_10.Checked = true;

        cb7_10.Checked = true;

        cb8_10.Checked = true;

        cb9_10.Checked = true;

        cb10_10.Checked = false;

        }

        }

        }

        Контрольный пример.

        Рассмотрим работу программы на конкретном примере.


        Заключение
        С помощью данной программы можно производить трассировку локальных сетей имеющих топологию дерево, с основным критерием «минимальная протяженность сети», с учетом необходимостей связи определенных комутирующих устройств.

        Список использованных источников
        Деньдобренько, Б.Н. Автоматизация конструирования РЭА [Текст]/Б.Н. Деньдобренько, А.С. Малика. – М.: Высш. школа, 1980.- 384 с.
      1. Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.// Proc. ASM. 1956. Vol 7, No. 1. C. 48-50
      2. http://www.ALGIB.sourse.ru



         Деньдобренько, Б.Н. Автоматизация конструирования РЭА

         Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. (перевод статьи)

         http://www.ALGIB.sourse.ru

перейти в каталог файлов


связь с админом