Размещено на http://www.allbest.ru/

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

Пензенский государственный университет

Кафедра "Вычислительная техника"

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

По курсовому проектированию

по курсу "Логика и основы алгоритмизации в инженерных задачах"

на тему "Поиск в графах"

Выполнил: студент Малинин Э.В.

Принял: д.т.н., профессор Пащенко Д.В.



Содержание

• Введение
• 1. Постановка задачи
• 2. Теоретическая часть
• 3. Описание программы
• 4. Отладка и тестирование
• Заключение
• Список используемых источников
• Приложение А. Листинги программы
• Приложение В. Результаты работы программы


Введение

Поиск в глубину - хороший инструмент для исследования топологических свойств графов. Например:

· В качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент.

· В топологической сортировке.

· Для поиска точек сочленения, мостов.

· В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока.

Поиск в глубину - естественный выбор, когда агент (человек или робот) лично ходит по лабиринту.



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

Написать программу для поиска всех путей в глубину.

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

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

Устройствами ввода информации являются клавиатура и мышь.

Программа должна быть разработана для работы в операционной системе Microsoft Windows.

2. Теоретическая часть

Начинаем поиск с некоторой фиксированной вершины v0, присвоим ей ПГ-номер: ПГ(v0)=1. Затем выбираем произвольную вершину w, смежную с v0, присваиваем ей ПГ-номер: ПГ(w)=2, и повторяем процесс уже от вершины w. Предположим, что в результате выполнения нескольких шагов этого процесса мы пришли в вершину v и пусть ПГ(v)=k. Далее действуем в зависимости от ситуации следующим образом:

1. Если имеется новая, т.е. еще непросмотренная вершина u, смежная с v, то, присваивая ей ПГ-номер: ПГ(u)=k+1, продолжаем поиск, начиная с вершины u;

2. Если же не существует ни одной новой, т.е. непросмотренной вершины u, смежной с v, то считаем, что вершина v просмотрена и возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс поиска дальше.

3. Поиск в глубину завершается, когда все вершины графа просмотрены. Если в результате работы алгоритма произошел возврат в начальную вершину v0, но при этом не все вершины графа просмотрены, то необходимо выбрать произвольную вершину из непросмотренных и продолжить процесс поиска от этой вершины.

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

граф алгоритм топологический интерфейс

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

Структура языка C++ позволяет наилучшим образом использовать возможности современных ЭВМ. На языке C++ программы обычно отличаются компактностью и быстротой исполнения. Программа, написанная на C++ для одной вычислительной системы, может быть перенесена с небольшими изменениями (или вообще без них) на другую.

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

Операции присваивания (=), инкрементации (++), декрементации (--) и другие возвращают значение. В сочетании с обилием операций это позволяет, хотя и не обязывает, создавать трудночитаемые выражения. Наличие этих операций в Си было вызвано желанием получить инструмент ручной оптимизации кода, но в настоящее время оптимизирующие компиляторы обычно генерируют оптимальный код и на традиционных выражениях.

C++ позволяет пропускать break в ветви оператора switch с целью последовательного выполнения нескольких ветвей. Такой же подход принят в языке Java. Есть мнение, что это затрудняет понимание кода.

В качестве среды программирования был выбран программный продукт от компании Microsoft Visual Studio 2013.

Для создания графического интерфейса использовались приложения Windows Form.

Интерфейс очень прост и состоит из не большего числа элементов, это кнопка генерации матрицы, кнопка запуска поиска, кнопка выхода из программы кнопка прорисовки графа, pictureBox для прорисовки, textbox: для задания количества вершин, для ввода стартовой вершины, для вывода информации; MessageBox для вывода ошибок, dataGridView для ввода матрицы. (Рис.3.1)

Рисунок 3.1 - Окно программы

Для запуска программы нужно ввести количество вершин в графе и нажать кнопку "Создание матрицы". Вводим смежность вершин. Выбираем стартовую вершину, от которой начинаем поиск, и нажимаем кнопку "Поиск". Получив необходимые данные, алгоритм начинает работу. Нажимаем кнопку "Рисуем" и граф изображается. В качестве результата выводится список вершин посещенных о стартовой.

Блок-схема программ (Рис. 3.2) показывает, как работает программа. После запуском основной функции поиска, инициализируется массив которые будут хранить информацию о заданном графе. Массив "Nachalo1" хранит массив матрицы смежности.

Рисунок 3.2 - Схема работы программы



4. Отладка и тестирование

В качестве среды разработки была выбрана программа Visual Studio 2013 которая содержит в себе все необходимые средства для разработки и отладки программы. Для отладки программы использовались наборы инструментов: точка остановки, пошаговое выполнение кода программы, анализ содержимого глобальных и локальных переменных.

Тестирование проводилось в процессе разработки и после написания программы.

В результате отладки программы выяснились, случаи в которых программа не выдавала ответ, либо отключается. Это связано с тем что при вводе были указаны символы, не принадлежащие к целочисленному типу данных, а также отрицательные числа. В таких случаях выводится сообщение (Рис. 4.1.).

Рисунок 4.1 - Сообщение об ошибке

При вводе целого положительно числа, происходит вывод программной вершин. (Рис 4.2-4.3) Если ввести иные символы, выведется сообщение об ошибке приведенное выше.



Рисунок 4.2 - Результаты работы программы

Рисунок 4.3 - Результаты работы программы



Заключение

При выполнении данной курсовой работы были получены базовые навыки программирования на языках С++, усовершенствованы навыки разработки многомодульных программ. Изучены основные возможности среды программирования Visual Studio 2013, получены навыки отладки и тестирования программ. Были рассмотрены некоторые функции из стандартной библиотеки языка С++. Были изучены базовые алгоритмы обработки данных.

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



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

1. Шилдт Г. Искусство программирования на C++. БХВ.2005

2. P. Лафоре - "Объектно-ориентированное программирование в С++"

3. Ф. Новиков - "Дискретная математика"

4. Р. Стивенс - "Алгоритмы. Теория и практическое применение"



Приложение А. Листинги программы

Файл MyFrom.cpp

#include "MyForm.h"

using namespace System;

using namespace System::Windows::Forms;

[STAThreadAttribute]

void Main(array<String^>^ args) {

Application::EnableVisualStyles();

Application::SetCompatibleTextRenderingDefault(false);

Проект 2::MyForm form;

Application::Run(%form);

}

Файл MyFrom.h

#pragma once

#include <cstdio>

#include <stdlib.h>

#include <conio.h>

#include <iostream>

#include <vector>

#include "conio.h"

#include "iostream"

#include "stdlib.h"

#include <stdio.h>

#include <tchar.h>

#include <cstdlib>

#include <SDKDDKVer.h>

#include "time.h"

#include "math.h"

#include "ffh.h"

namespace Проект 2 {

using namespace System;

using namespace System::ComponentModel;

using namespace System::Collections;

using namespace System::Windows::Forms;

using namespace System::Data;

using namespace System::Drawing;

/// <summary>

/// Сводка для MyForm

/// </summary>

public ref class MyForm : public System::Windows::Forms::Form

{

public:

MyForm(void)

{

InitializeComponent();

//

//TODO: добавьте код конструктора

//

}

protected:

/// <summary>

/// Освободить все используемые ресурсы.

/// </summary>

~MyForm()

{

if (components)

{

delete components;

}

}

private: System::Windows::Forms::Button^ button1;

internal: System::Windows::Forms::Button^ button2;

private:

protected:

private: System::Windows::Forms::TextBox^ textBox1;

private: System::Windows::Forms::Label^ label1;

private: System::Windows::Forms::Label^ label2;

private: System::Windows::Forms::Label^ label3;

private: System::Windows::Forms::Label^ label4;

private: System::Windows::Forms::ErrorProvider^ errorProvider1;

private: System::Windows::Forms::ErrorProvider^ errorProvider2;

protected: System::Windows::Forms::DataGridView^ dataGridView1;

private:

private: System::Windows::Forms::Label^ label5;

private: System::Windows::Forms::TextBox^ textBox2;

private: System::Windows::Forms::Button^ button3;

private: System::Windows::Forms::TextBox^ textBox3;

private: System::Windows::Forms::Button^ button4;

private: System::Windows::Forms::PictureBox^ pictureBox1;

private: System::Windows::Forms::Label^ label6;

private: System::ComponentModel::IContainer^ components;

private:

/// <summary>

/// Обязательная переменная конструктора.

/// </summary>

#pragma region Windows Form Designer generated code

/// <summary>

/// Требуемый метод для поддержки конструктора - не изменяйте

/// содержимое этого метода с помощью редактора кода.

/// </summary>

void InitializeComponent(void)

{

this->components = (gcnew System::ComponentModel::Container());

System::ComponentModel::ComponentResourceManager^ resources = (gcnew System::ComponentModel::ComponentResourceManager(MyForm::typeid));

this->button1 = (gcnew System::Windows::Forms::Button());

this->button2 = (gcnew System::Windows::Forms::Button());

this->textBox1 = (gcnew System::Windows::Forms::TextBox());

this->label1 = (gcnew System::Windows::Forms::Label());

this->label2 = (gcnew System::Windows::Forms::Label());

this->label3 = (gcnew System::Windows::Forms::Label());

this->label4 = (gcnew System::Windows::Forms::Label());

this->errorProvider1 = (gcnew System::Windows::Forms::ErrorProvider(this->components));

this->errorProvider2 = (gcnew System::Windows::Forms::ErrorProvider(this->components));

this->button3 = (gcnew System::Windows::Forms::Button());

this->textBox2 = (gcnew System::Windows::Forms::TextBox());

this->label5 = (gcnew System::Windows::Forms::Label());

this->dataGridView1 = (gcnew System::Windows::Forms::DataGridView());

this->textBox3 = (gcnew System::Windows::Forms::TextBox());

this->label6 = (gcnew System::Windows::Forms::Label());

this->pictureBox1 = (gcnew System::Windows::Forms::PictureBox());

this->button4 = (gcnew System::Windows::Forms::Button());

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->errorProvider1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->errorProvider2))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->dataGridView1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->pictureBox1))->BeginInit();

this->SuspendLayout();

//

// button1

//

this->button1->BackColor = System::Drawing::Color::Lime;

this->button1->BackgroundImageLayout = System::Windows::Forms::ImageLayout::Center;

this->button1->Cursor = System::Windows::Forms::Cursors::Hand;

this->button1->FlatStyle = System::Windows::Forms::FlatStyle::Popup;

this->button1->ForeColor = System::Drawing::Color::Red;

this->button1->Location = System::Drawing::Point(294, 130);

this->button1->Margin = System::Windows::Forms::Padding(4);

this->button1->Name = L"button1";

this->button1->Size = System::Drawing::Size(182, 60);

this->button1->TabIndex = 0;

this->button1->Text = L"Создание матрицы";

this->button1->TextImageRelation = System::Windows::Forms::TextImageRelation::ImageBeforeText;

this->button1->UseVisualStyleBackColor = false;

this->button1->Click += gcnew System::EventHandler(this, &MyForm::button1_Click);

//

// button2

//

this->button2->AccessibleRole = System::Windows::Forms::AccessibleRole::Grip;

this->button2->Anchor = static_cast<System::Windows::Forms::AnchorStyles>(((System::Windows::Forms::AnchorStyles::Top | System::Windows::Forms::AnchorStyles::Bottom)

| System::Windows::Forms::AnchorStyles::Left));

this->button2->AutoSizeMode = System::Windows::Forms::AutoSizeMode::GrowAndShrink;

this->button2->BackColor = System::Drawing::Color::Lime;

this->button2->Cursor = System::Windows::Forms::Cursors::Hand;

this->button2->FlatStyle = System::Windows::Forms::FlatStyle::Popup;

this->button2->ForeColor = System::Drawing::Color::Black;

this->button2->Location = System::Drawing::Point(594, 603);

this->button2->Margin = System::Windows::Forms::Padding(1);

this->button2->Name = L"button2";

this->button2->Size = System::Drawing::Size(104, 40);

this->button2->TabIndex = 1;

this->button2->Text = L"Выход";

this->button2->TextImageRelation = System::Windows::Forms::TextImageRelation::ImageBeforeText;

this->button2->UseVisualStyleBackColor = false;

this->button2->Click += gcnew System::EventHandler(this, &MyForm::button2_Click);

//

// textBox1

//

this->textBox1->ForeColor = System::Drawing::SystemColors::ControlText;

this->textBox1->Location = System::Drawing::Point(246, 96);

this->textBox1->Margin = System::Windows::Forms::Padding(4);

this->textBox1->Name = L"textBox1";

this->textBox1->Size = System::Drawing::Size(295, 26);

this->textBox1->TabIndex = 2;

this->textBox1->TextChanged += gcnew System::EventHandler(this, &MyForm::textBox1_TextChanged);

//

// label1

//

this->label1->AutoSize = true;

this->label1->Font = (gcnew System::Drawing::Font(L"Times New Roman", 15));

this->label1->ForeColor = System::Drawing::Color::Black;

this->label1->Location = System::Drawing::Point(287, 9);

this->label1->Margin = System::Windows::Forms::Padding(4, 0, 4, 0);

this->label1->Name = L"label1";

this->label1->Size = System::Drawing::Size(189, 22);

this->label1->TabIndex = 8;

this->label1->Text = L"ОБХОД В ГЛУБИНУ";

this->label1->TextAlign = System::Drawing::ContentAlignment::MiddleCenter;

this->label1->Click += gcnew System::EventHandler(this, &MyForm::label1_Click);

//

// label2

//

this->label2->AutoSize = true;

this->label2->BackColor = System::Drawing::Color::Firebrick;

this->label2->Font = (gcnew System::Drawing::Font(L"Times New Roman", 13.8F, System::Drawing::FontStyle::Italic, System::Drawing::GraphicsUnit::Point,

static_cast<System::Byte>(204)));

this->label2->ForeColor = System::Drawing::Color::Black;

this->label2->Location = System::Drawing::Point(50, 96);

this->label2->Margin = System::Windows::Forms::Padding(4, 0, 4, 0);

this->label2->Name = L"label2";

this->label2->Size = System::Drawing::Size(182, 48);

this->label2->TabIndex = 879;

this->label2->Tag = L"88";

this->label2->Text = L"Количество вершин:\r\n\r\n";

this->label2->UseCompatibleTextRendering = true;

this->label2->Click += gcnew System::EventHandler(this, &MyForm::label2_Click);

//

// label3

//

this->label3->AutoSize = true;

this->label3->ForeColor = System::Drawing::Color::Black;

this->label3->Location = System::Drawing::Point(12, 452);

this->label3->Name = L"label3";

this->label3->Size = System::Drawing::Size(147, 19);

this->label3->TabIndex = 880;

this->label3->Text = L"Старшая вершина:\r\n";

this->label3->Click += gcnew System::EventHandler(this, &MyForm::label3_Click);

//

// label4

//

this->label4->AutoSize = true;

this->label4->ForeColor = System::Drawing::Color::Black;

this->label4->Location = System::Drawing::Point(32, 194);

this->label4->Name = L"label4";

this->label4->Size = System::Drawing::Size(170, 19);

this->label4->TabIndex = 884;

this->label4->Text = L"Матрица смежности:";

this->label4->Click += gcnew System::EventHandler(this, &MyForm::label4_Click);

//

// errorProvider1

//

this->errorProvider1->ContainerControl = this;

//

// errorProvider2

//

this->errorProvider2->ContainerControl = this;

//

// button3

//

this->button3->BackColor = System::Drawing::Color::Lime;

this->button3->ForeColor = System::Drawing::Color::Black;

this->button3->Location = System::Drawing::Point(246, 503);

this->button3->Name = L"button3";

this->button3->Size = System::Drawing::Size(75, 23);

this->button3->TabIndex = 886;

this->button3->Text = L"Поиск";

this->button3->UseVisualStyleBackColor = false;

this->button3->Click += gcnew System::EventHandler(this, &MyForm::button3_Click);

//

// textBox2

//

this->textBox2->Location = System::Drawing::Point(181, 452);

this->textBox2->Name = L"textBox2";

this->textBox2->Size = System::Drawing::Size(150, 26);

this->textBox2->TabIndex = 887;

this->textBox2->TextChanged += gcnew System::EventHandler(this, &MyForm::textBox2_TextChanged_1);

//

// label5

//

this->label5->AutoSize = true;

this->label5->ForeColor = System::Drawing::Color::Black;

this->label5->Location = System::Drawing::Point(12, 554);

this->label5->Name = L"label5";

this->label5->Size = System::Drawing::Size(127, 19);

this->label5->TabIndex = 888;

this->label5->Text = L"Обход в глубину:\r\n";

this->label5->Click += gcnew System::EventHandler(this, &MyForm::label5_Click);

//

// dataGridView1

//

this->dataGridView1->BackgroundColor = System::Drawing::Color::WhiteSmoke;

this->dataGridView1->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;

this->dataGridView1->GridColor = System::Drawing::SystemColors::ActiveCaptionText;

this->dataGridView1->Location = System::Drawing::Point(57, 226);

this->dataGridView1->Name = L"dataGridView1";

this->dataGridView1->Size = System::Drawing::Size(295, 204);

this->dataGridView1->TabIndex = 890;

this->dataGridView1->CellContentClick += gcnew System::Windows::Forms::DataGridViewCellEventHandler(this, &MyForm::dataGridView1_CellContentClick);

//

// textBox3

//

this->textBox3->Location = System::Drawing::Point(181, 554);

this->textBox3->Name = L"textBox3";

this->textBox3->Size = System::Drawing::Size(150, 26);

this->textBox3->TabIndex = 891;

this->textBox3->TextChanged += gcnew System::EventHandler(this, &MyForm::textBox3_TextChanged);

//

// label6

//

this->label6->AutoSize = true;

this->label6->ForeColor = System::Drawing::Color::Black;

this->label6->Location = System::Drawing::Point(386, 194);

this->label6->Name = L"label6";

this->label6->Size = System::Drawing::Size(142, 19);

this->label6->TabIndex = 892;

this->label6->Text = L"Прорисовка графа:\r\n";

//

// pictureBox1

//

this->pictureBox1->BackColor = System::Drawing::Color::White;

this->pictureBox1->Location = System::Drawing::Point(370, 226);

this->pictureBox1->Name = L"pictureBox1";

this->pictureBox1->Size = System::Drawing::Size(358, 354);

this->pictureBox1->TabIndex = 893;

this->pictureBox1->TabStop = false;

//

// button4

//

this->button4->BackColor = System::Drawing::Color::Lime;

this->button4->ForeColor = System::Drawing::Color::Black;

this->button4->Location = System::Drawing::Point(594, 194);

this->button4->Name = L"button4";

this->button4->Size = System::Drawing::Size(75, 26);

this->button4->TabIndex = 894;

this->button4->Text = L"Рисуем\r\n";

this->button4->UseVisualStyleBackColor = false;

this->button4->Click += gcnew System::EventHandler(this, &MyForm::button4_Click);

//

// MyForm

//

this->AutoScaleDimensions = System::Drawing::SizeF(9, 19);

this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;

this->BackColor = System::Drawing::Color::FromArgb(static_cast<System::Int32>(static_cast<System::Byte>(192)), static_cast<System::Int32>(static_cast<System::Byte>(0)),

static_cast<System::Int32>(static_cast<System::Byte>(0)));

this->BackgroundImageLayout = System::Windows::Forms::ImageLayout::Stretch;

this->ClientSize = System::Drawing::Size(740, 733);

this->Controls->Add(this->button4);

this->Controls->Add(this->pictureBox1);

this->Controls->Add(this->label6);

this->Controls->Add(this->textBox3);

this->Controls->Add(this->dataGridView1);

this->Controls->Add(this->label5);

this->Controls->Add(this->textBox2);

this->Controls->Add(this->button3);

this->Controls->Add(this->label4);

this->Controls->Add(this->label3);

this->Controls->Add(this->label2);

this->Controls->Add(this->label1);

this->Controls->Add(this->textBox1);

this->Controls->Add(this->button2);

this->Controls->Add(this->button1);

this->Font = (gcnew System::Drawing::Font(L"Times New Roman", 12, static_cast<System::Drawing::FontStyle>((System::Drawing::FontStyle::Bold | System::Drawing::FontStyle::Italic)),

System::Drawing::GraphicsUnit::Point, static_cast<System::Byte>(204)));

this->ForeColor = System::Drawing::Color::PeachPuff;

this->Icon = (cli::safe_cast<System::Drawing::Icon^>(resources->GetObject(L"$this.Icon")));

this->Margin = System::Windows::Forms::Padding(4);

this->Name = L"MyForm";

this->Text = L"Обход в глубину";

this->TransparencyKey = System::Drawing::Color::Yellow;

this->Load += gcnew System::EventHandler(this, &MyForm::MyForm_Load);

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->errorProvider1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->errorProvider2))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->dataGridView1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->pictureBox1))->EndInit();

this->ResumeLayout(false);

this->PerformLayout();

}

#pragma endregion

private: System::Void textBox1_TextChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void label1_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void label2_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void MyForm_Load(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {

Single Nachalo;

bool Proverka = Single::TryParse(textBox1->Text,

System::Globalization::NumberStyles::Number,

System::Globalization::NumberFormatInfo::CurrentInfo, Nachalo);;

if (Proverka == false) {

MessageBox::Show(

"Ошибка ввода",

"Сообщение",

MessageBoxButtons::OK,

MessageBoxIcon::Information);

return;

}

if (Nachalo <=0) {

MessageBox::Show(

"Ошибка ввода",

"Сообщение",

MessageBoxButtons::OK,

MessageBoxIcon::Information);

return;

}

int **mass = new int *[Nachalo];

for (int i = 0; i < Nachalo; i++)

{

mass[i] = new int[Nachalo];

}

dataGridView1->ColumnCount = Nachalo;

dataGridView1->RowCount = Nachalo;

for (int i = 0; i < Nachalo; i++)

{

for (int j = 0; j < Nachalo; j++)

{

mass[i][j] = Convert::ToDouble(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

for (int i; i<Nachalo; i++)

{

for (int j = 0; j < Nachalo; j++)

{

dataGridView1->TopLeftHeaderCell->Value = "Матрица смежности";

dataGridView1->Columns[j]->HeaderCell->Value = Convert::ToString(j + 1);

dataGridView1->Rows[i]->HeaderCell->Value = Convert::ToString(i + 1);

dataGridView1->Rows[i]->Cells[j]->Value = mass[i][j];

}

}

dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView1->AutoResizeColumns();

for (int i = 0; i < Nachalo; i++)

{

delete[] mass[i];

}

delete[] mass;

}

private: System::Void textBox2_TextChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void listBox1_SelectedIndexChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) {

Application::Exit();

}

private: System::Void label4_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void numericUpDown1_ValueChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void label3_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void label5_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e) {

Single Nachalo;

bool Proverka = Single::TryParse(textBox1->Text,

System::Globalization::NumberStyles::Number,

System::Globalization::NumberFormatInfo::CurrentInfo, Nachalo);;

Single Starsh;

bool Proverka1 = Single::TryParse(textBox2->Text,

System::Globalization::NumberStyles::Number,

System::Globalization::NumberFormatInfo::CurrentInfo, Starsh);;

A = new int*[Nachalo];

for (int i = 0; i < Nachalo; i++) {

A[i]= new int[Nachalo];

}

for (int i = 0; i < Nachalo; i++) {

for (int j = 0; j < Nachalo; j++){

A[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

Nachalo1 = Nachalo;

if (Proverka1 == false) {

MessageBox::Show(

"Ошибка ввода",

"Сообщение",

MessageBoxButtons::OK,

MessageBoxIcon::Information);

return;

}

if (Starsh<= 0) {

MessageBox::Show(

"Ошибка ввода",

"Сообщение",

MessageBoxButtons::OK,

MessageBoxIcon::Information);

return;

}

graph = new int*[Nachalo];

for (int i = 0; i < Nachalo; i++) {

graph[i] = new int[Nachalo];

}

Header a;

a.Show(Starsh,Nachalo);

for (int p = 0; p < s; p++)

textBox3->Text += Convert::ToString(otvet[p]);

}

private: System::Void textBox2_TextChanged_1(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void textBox3_TextChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void dataGridView1_CellContentClick(System::Object^ sender, System::Windows::Forms::DataGridViewCellEventArgs^ e) {

}

private: System::Void button4_Click(System::Object^ sender, System::EventArgs^ e) {

int *a, *b;

int n = System::Convert::ToDouble(textBox1->Text);

int i = 0;

unsigned c = 0;

A = new int*[n];

for (int i = 0; i < n; i++) {

A[i] = new int[n];

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

A[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

int j, z, x, k = 0;

int u[10];

srand(time(0));

x = 0;

Graphics^ gr = this->pictureBox1->CreateGraphics();

a = (int*)malloc(n * sizeof(int));

b = (int*)malloc(n * sizeof(int));

for (int c1 = 0; c1<n; c1++)

{

int secret = rand() % 8;

c = c + 1;

srand(c);

if (secret == 0)

{

a[c1] = 100 + secret * 20;

b[c1] = 100 + secret * 20;

}

if (secret == 1)

{

a[c1] = 300 - secret * 20;

b[c1] = 300 + secret * 20;

}

if (secret == 2)

{

a[c1] = 400 - secret * 10;

b[c1] = 400 - secret * 10;

}

if (secret == 3)

{

a[c1] = 400 - secret * 10;

b[c1] = 50 - secret * 10;

}

if (secret == 4)

{

a[c1] = 300 - secret * 15;

b[c1] = 100 + secret * 15;

}

if (secret == 5)

{

a[c1] = 200 + secret * 5;

b[c1] = 350 - secret * 10;

}

if (secret == 6)

{

a[c1] = 35 + secret * 10;

b[c1] = 350 + secret * 15;

}

if (secret == 7)

{

a[c1] = 400 - secret * 20;

b[c1] = 150 - secret * 5;

}

}

int counter = 0;

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

{

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

{

String^ Text = Text->Format("{0} ", j + 1);

String^ Loop = Text->Format("{0}", A[i][j]);

Brush^ Кисть = gcnew SolidBrush(Color::DarkGreen);

Brush^ неКисть = gcnew SolidBrush(Color::DarkGreen);

if (i == 0 && j == 0)

{

gr->DrawString(Text, Font, Кисть, a[i], b[j]);

gr->DrawEllipse(System::Drawing::Pens::Green, a[i] - 2, b[j] - 2, 4, 4);

}

gr->TextRenderingHint = System::Drawing::Text::TextRenderingHint::AntiAlias;

if (i == counter && j != 0)

{

gr->DrawString(Text, Font, Кисть, a[j], b[j]);

gr->DrawEllipse(System::Drawing::Pens::YellowGreen, a[j] - 2, b[j] - 2, 4, 4);

if (A[i][j] != 0)

{

gr->DrawLine(System::Drawing::Pens::YellowGreen, a[i], b[i], a[j], b[j]);

gr->DrawEllipse(System::Drawing::Pens::YellowGreen, a[i] - 2, b[i] - 2, 4, 4);

gr->DrawString(Text, Font, Кисть, a[j], b[j]);

gr->DrawString(Loop, Font, неКисть, (a[j] + a[i]) / 2, (b[j] + b[i]) / 2);

}

}

}

counter++;

}

}

};

}

Файл ffh.h

#pragma once

#include <cstdio>

#include <stdlib.h>

#include <conio.h>

#include <iostream>

#include <stdio.h>

#include <vector>

#include "MyForm.h"

class Header {

private:

int i, j;

public:

void Show(int start, int Nachalo);

void DFS(std::vector<bool> &visited, int unit);

};

int Nachalo1;

int **graph;

int *otvet = new int[Nachalo1];

int s=0;

void Header::DFS(std::vector<bool> &visited, int unit) {

std::vector <int> queue(Nachalo1, 0);

int count = 0;

int head = 0;

queue[count++] = unit; //стартовая вершина помещается в "очередь"

visited[unit] = true; //вершина помечается как посещенная

unit = queue[head++];

otvet[s] = unit+1;

s++;

int to = 0;

for (i = 0; i < Nachalo1; i++) {

if ((graph[unit][i] != 0) && (!visited[i])) {

DFS(visited, i);

}

}

}

void Header::Show(int start, int Nachalo) {

std::vector <bool> visited(Nachalo);

DFS(visited, start - 1);

return;

}



Приложение В. Результаты работы программы

Рисунок 4.4 - Результаты работы программы

Рисунок 4.5 - Результаты работы программы

Размещено на Allbest.ru

...