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

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



Введение

Актуальность задачи о максимальном потоке постоянно возрастает вместе со строительством трубопроводов, новых дорог, роста пользователей Интернета и любых других сетей. Поэтому быстрое и точное её решение крайне необходимо во всех сферах нашей деятельности, где хоть как-то встает вопрос об перемещение чего-либо куда-либо с максимальной рациональностью.

Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира. 60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе.

В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974г. Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы.

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

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

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

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

Разработка будет осуществляться с использованием среды программирования MSVisualStudio. Созданная программа будет ориентирована на операционную систему MSWindows.



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

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

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

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

В дальнейшем будем рассматривать только простые графы, опуская при этом слово простые.

Если (u,v) - некоторое ребро графа G, то вершины u и v называются смежными, а вершины u и ребро (u,v), также как вершина v и ребро (u,v), называются инцидентными друг другу. Степенью вершины v в графе G называется число ребер графа G, инцидентных вершине v.

Пример графа представлен на рисунке 1.

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

В данном примере:

V = {v1, v2, v3, v4, v5, v6},

E = {(v1, v2), (v2, v3), (v1, v3), (v3, v4), (v4, v5), (v4, v6), (v5, v6)}

Пусть G = (V, E) - некоторый граф, u и v - его вершины. Маршрутом в графе G, соединяющим вершины u и v, называется конечная чередующаяся последовательность вершин и ребер вида v1, e1, v2, e2,...,ek-1, vk, где v1,...,vk из V, а e1,...,ek-1 из E. Маршрут называют цепью, если все его ребра различны. Цепь называют путем (или простой цепью), если все ее вершины кроме, быть может, концевых различны. Если начальная и конечная вершина пути совпадают, то его называют замкнутым путем или циклом.

Граф называется связным графом, если для любых двух его вершин существует соединяющий их маршрут.

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

Ориентированным графом D называется пара (V, A), где V - непустое конечное множество, элементы которого называются вершинами графа, а A - конечное множество упорядоченных пар различных элементов из V, элементы множества A называются дугами.

Подобно графам для ориентированных графов вводятся понятие смежности вершин, понятие инцидентности и так далее.

Основанием ориентированного графа D = (V, A), называется граф G = (V, E), где E = A, то есть упорядоченные пары вершин заменяются на неупорядоченные.

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(), называемое пропускной способностью дуги, и существует:

1) ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети;

2) ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга называется насыщеннойпотоком f, если (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)

Разрезом L сети G(V,E) называется множество насыщенных дуг, отделяющих источник s от стока t.

поток транспортный граф

2.2 Поток в транспортной сети

Функция , определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:

*для любой дуги величина , называемая потоком по дуге , удовлетворяет условию ;

*для любой промежуточной вершины v выполняется равенство

т.е. сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.

Для любого допустимого потока в транспортной сети D выполняется равенство:

По определению допустимого потока имеем:

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

Аналогично для каждой дуги , величина входит в левую часть равенства (2) лишь один раз и при этом со знаком минус. С другой стороны, для каждой дуги величина входит в левую часть равенства (2) один раз со знаком плюс (при ) и один раз со знаком минус (при ), что в сумме даёт нулевой вклад в левую часть равенства (2). Учитывая сказанное, заключаем, что из равенства (2) следует справедливость равенства (1).

Величиной потока в транспортной сети D называется величина , равная сумме потоков по всем дугам, заходящим в , или, что то же самое - величина, равная сумме потоков по всем дугам, исходящим из



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

Поток называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

Очевидно, что максимальный поток обязательно является полным (т.к. в противном случае в D существует некоторая простая цепь из V1 в Vn, не содержащая насыщенных дуг, а следовательно, можно увеличить на единицу потоки по всем дугам из и тем самым увеличить на единицу , что противоречит условию максимальности потока). Обратная же, вообще говоря, неверно. Существуют полные потоки, не являющиеся максимальными. Тем на менее полный поток можно рассматривать как некоторое приближение к максимальному потоку.

2.3 Орграф приращений

Введем для заданной транспортной сети D и допустимого потока в этой сети орграф приращений , имеющий те же вершины, что и сеть D. Каждой дуге транспортной сети D в орграфе приращений соответствует две дуги: и - дуга, противоположная по направлению дуге . Припишем дугам орграфа приращений длину:

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

2.4 Теорема Форда-Фалкерсона

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

Пусть . Тогда выполняется равенство

(1)

Если , так как в противном случае, используя имеем , а следовательно, в силу существует путь нулевой длины из в , что противоречит условию . Но тогда из (1) получаем

Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина максимального потока в транспортной сети равна пропускной способности минимального разреза.

Следствие 2. Пусть - допустимый поток в транспортной сети D. Тогда, если длина минимального пути из v1 в vn в орграфе приращений равна бесконечности, то - максимальный поток.



3.Описание алгоритма решения поставленной задачи

Важным следствием теоремы Форда-Фалкерсона является алгоритм построения максимального потока в транспортной сети.

Шаг 1. Полагаем i=0. Пусть - любой допустимый поток в транспортной сети D (например, полный, можно начинать с нулевого потока: ).

Шаг 2.По сети D и потоку строим орграф приращений .

Шаг 3.Находим простую цепь , являющуюся минимальным путем из в в нагруженном орграфе . Если длина этой цепи равна бесконечности, то поток максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи на максимально допустимую величину , такую, что при этом сохраняется условие 1 допустимого потока (для любой дуги величина , называемая потоком по дуге х, удовлетворяет условию ). В силу , используя и , получаем, что указанная величина существует. В результате меняется поток в транспортной сети D, т.е. от потока мы перешли к потоку , и при этом . Присваиваем и переходим к шагу 2.

Программа должна находить максимальный поток во введенную в неё транспортной сети. Блок-схема данного алгоритма представлена на рис.2.

Рис.2. Блок-схема алгоритма.

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

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

Внизу главного окна располагается текстовое поле вывода значения максимального потока и кнопка запуска решения по алгоритму Форда-Фалкерсона. В правой части находится окно вывода графа. Пример окна демонстрируется на рис.3,4. Взаимодействие компонентов указывается на рис.5.

Рис.3. Исходное состояние

Рис.4. Результат работы

Рис.5. Схема данных



5.Тесты

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

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

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

Если пользователь неправильно вводит исходную матрицу смежности (вводит текстовые), то выдаётся окно с ошибкой «Ошибка ввода матрицы смежности». Пример такого окна показан на рис.6.

Рис.6. Пример неверно введенных данных



Заключение

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

При выполнении данной работы использовались функции WindowsForms для визуализации результатов работы.

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



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

1.Шаблоны С++ Справочник разработчика: Дэвид Вандевурд, Николаи М. Джосаттис, Москва - Санкт-Петербург - Киев, 2003г.

2.Самоучитель С++: Шилат Г. Пер с англ. - 3-е изд - СПб; БХВ- Петербург, 2005.-688 с.

3.Основы программирования на С++: Стенли Б. Липпман, Издательский дом "Вильямс" Москва - Санкт-Петербург - Киев 2002 г.

4.Ресурсы электронной библиотеки http://msdn.microsoft.com/

5.Основы теории графов: Зыков А.А. -Москва, Наука, 1987г. - 381 с.



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

Файл «MyForm.cpp»

#include "MyForm.h"

using namespace System;

using namespace System::Windows::Forms;

[STAThreadAttribute]

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

Application::EnableVisualStyles();

Application::SetCompatibleTextRenderingDefault(false);

NewHope::MyForm form;

Application::Run(%form);

}

Файл «MyForm.h»

#pragma once

#include "Header.h"

int **mass;

int *a;

int *b;

constint MAX_VERTICES = 40;

int NUM_VERTICES; // числовершин в графе

constintinfinity = 10000; // условное число обозначающее бесконечность

// f - массив содержащий текушее значение потока// f[i][j] - поток текущий от вершины i к j

int f[MAX_VERTICES][MAX_VERTICES];

// с - массив содержащий вместимоти ребер,

// т.е. c[i][j] - максимальная величину потока способная течь по ребру (i,j)

intcp[MAX_VERTICES][MAX_VERTICES];

// набор вспомогательных переменных используемых функцией FindPath - обхода в ширину

// Flow - значение потока чарез данную вершину на данном шаге поиска

intFlow[MAX_VERTICES];

// Link используется для нахождения собственно пути

// Link[i] хранит номер предыдущей вешины на пути i -> исток

intLink[MAX_VERTICES];

intQP, QC; // QP - указатель начала очереди и QC - число эл-тов в очереди

// поск пути по которому возможно пустить поток алгоритмом обхода графа в ширину// функция ищет путь из истока в сток по которому еще можно пустить поток,

// считая вместимость ребера (i,j) равной c[i][j] - f[i][j],

// т.е. после каждой итерации(одна итерация - один поик пути) уменьшаем вместимости ребер,// на величину пущеного потока

namespace NewHope {

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;

protected:

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

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

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

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

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

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

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

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

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

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

private:

/// <summary>

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

/// </summary>

System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code

/// <summary>

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

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

/// </summary>

void InitializeComponent(void)

{

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

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

this->num = (gcnewSystem::Windows::Forms::TextBox());

this->maxpotok = (gcnewSystem::Windows::Forms::TextBox());

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

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

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

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

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

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

this->button5 = (gcnewSystem::Windows::Forms::Button());

(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::Black;

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

this->button1->ForeColor = System::Drawing::SystemColors::Window;

this->button1->Location = System::Drawing::Point(252, 25);

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

this->button1->Size = System::Drawing::Size(178, 23);

this->button1->TabIndex = 0;

this->button1->Text = L"Заполнитьматрицусмежности";

this->button1->UseVisualStyleBackColor = false;

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

//

// label1

//

this->label1->AutoSize = true;

this->label1->Location = System::Drawing::Point(12, 7);

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

this->label1->Size = System::Drawing::Size(138, 13);

this->label1->TabIndex = 1;

this->label1->Text = L"Введитеразмерматрицы";

//

// num

//

this->num->Location = System::Drawing::Point(15, 27);

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

this->num->Size = System::Drawing::Size(231, 20);

this->num->TabIndex = 2;

//

// maxpotok

//

this->maxpotok->Location = System::Drawing::Point(173, 470);

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

this->maxpotok->Size = System::Drawing::Size(164, 20);

this->maxpotok->TabIndex = 5;

//

// dataGridView1

//

this->dataGridView1->BackgroundColor = System::Drawing::SystemColors::ControlLightLight;

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

this->dataGridView1->Location = System::Drawing::Point(15, 54);

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

this->dataGridView1->Size = System::Drawing::Size(415, 344);

this->dataGridView1->TabIndex = 6;

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

//

// label2

//

this->label2->AutoSize = true;

this->label2->Location = System::Drawing::Point(15, 473);

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

this->label2->Size = System::Drawing::Size(152, 13);

this->label2->TabIndex = 7;

this->label2->Text = L"Максимальныйпотокграфа";

//

// button2

//

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

this->button2->Location = System::Drawing::Point(15, 404);

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

this->button2->Size = System::Drawing::Size(415, 50);

this->button2->TabIndex = 8;

this->button2->Text = L"Найтимаксимальныйпоток";

this->button2->UseVisualStyleBackColor = true;

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

//

// button3

//

this->button3->Location = System::Drawing::Point(860, 25);

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

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

this->button3->TabIndex = 9;

this->button3->Text = L"Очиститьматрицу";

this->button3->UseVisualStyleBackColor = true;

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

//

// pictureBox1

//

this->pictureBox1->BackColor = System::Drawing::SystemColors::HighlightText;

this->pictureBox1->Location = System::Drawing::Point(436, 54);

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

this->pictureBox1->Size = System::Drawing::Size(539, 344);

this->pictureBox1->TabIndex = 10;

this->pictureBox1->TabStop = false;

//

// button4

//

this->button4->Location = System::Drawing::Point(436, 404);

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

this->button4->Size = System::Drawing::Size(275, 50);

this->button4->TabIndex = 11;

this->button4->Text = L"Нарисоватьграф";

this->button4->UseVisualStyleBackColor = true;

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

//

// button5

//

this->button5->Location = System::Drawing::Point(717, 404);

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

this->button5->Size = System::Drawing::Size(258, 50);

this->button5->TabIndex = 12;

this->button5->Text = L"Очиститьполе";

this->button5->UseVisualStyleBackColor = true;

this->button5->Click += gcnewSystem::EventHandler(this, &MyForm::button5_Click);

//

// MyForm

//

this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);

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

this->BackColor = System::Drawing::Color::WhiteSmoke;

this->ClientSize = System::Drawing::Size(982, 503);

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

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

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

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

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

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

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

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

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

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

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

this->Name = L"MyForm";

this->Text = L"Максимальныйпотокграфа";

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

(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 MyForm_Load(System::Object^ sender, System::EventArgs^ e) {

}

public: void typing(int n, int **mass)

{

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

{

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

{

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

cp[i][j] = mass[i][j];

}

}

}

private: void clear()

{

for (inti = 0; i < dataGridView1->Rows->Count; i++)

{

dataGridView1->Rows[0]->Cells[i]->Value = 0;

for (int j = 0; j < dataGridView1->Rows->Count; j++)

{

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

}

}

}

private: void show(int n, int **mass)

{

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

{

for (int j = 0; j < n; 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];

}

}

}

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

{

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

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

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

{

mass[i] = new int[n];

}

dataGridView1->ColumnCount = n;

dataGridView1->RowCount = n;

typing(n, mass);

show(n, mass);

dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView1->AutoResizeColumns();

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

{

delete[] mass[i];

}

delete[] mass;

}

private: intFindPath(int source, int target) // source - исток, target - сток

{

int Queue[MAX_VERTICES]; // Очередь

QP = 0; QC = 1; Queue[0] = source;

Link[target] = -1; // особая метка для стока

inti;

intCurVertex;

memset(Flow, 0, sizeof(int)*NUM_VERTICES); // в началеизвсехвершинкромеистокатечет 0

Flow[source] = infinity; // а из истока может вытечь сколько угодно

while (Link[target] == -1 && QP < QC)

{

// смотрим какие вершины могут быть достигнуты из начала очереди

CurVertex = Queue[QP];

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

// проверяем можем ли мы пустить поток по ребру (CurVertex,i):

if ((cp[CurVertex][i] - f[CurVertex][i])>0 && Flow[i] == 0)

{

// если можем, то добавляем i в конец очереди

Queue[QC] = i; QC++;

Link[i] = CurVertex; // указываем, что в i добрались из CurVertex

// и находим значение потока текущее через вершину i

if (cp[CurVertex][i] - f[CurVertex][i] < Flow[CurVertex])

Flow[i] = cp[CurVertex][i];

else

Flow[i] = Flow[CurVertex];

}

QP++;// прерходим к следующей в очереди вершине

}

// закончив поиск пути

if (Link[target] == -1) return 0; // мы или не находим путь и выходим

// или находим:

// тогда Flow[target] будет равен потоку который "дотек" по данному пути из истока в сток

// тогда изменяем значения массива f для данного пути на величину Flow[target]

CurVertex = target;

while (CurVertex != source) // путь из стока в исток мы восстанавливаем с помощбю массива Link

{

f[Link[CurVertex]][CurVertex] += Flow[target];

CurVertex = Link[CurVertex];

}

returnFlow[target]; // Возвращаем значение потока которое мы еще смогли "пустить" по графу

}

public: intMaxFlow(int source, int target) // source - исток, target - сток

{

// инициализируемпеременные:

memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTICES); // пографуничегонетечет

intMaxFlow = 0; // начальное значение потока

intAddFlow;

do

{

// каждую итерацию ищем какй-либо простой путь из истока в сток

// и какой еще поток мажет быть пущен по этому пути

AddFlow = FindPath(source, target);

MaxFlow += AddFlow;

} while (AddFlow>0);// повторяем цикл пока поток увеличивается

return MaxFlow;

}

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

{

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

int target = n - 1; int source = 0;

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

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

{

mass[i] = new int[n];

}

dataGridView1->ColumnCount = n;

dataGridView1->RowCount = n;

typing(n, mass);

show(n, mass);

NUM_VERTICES = n;

dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView1->AutoResizeColumns();

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

{

delete[] mass[i];

}

delete[] mass;

maxpotok->Text = System::Convert::ToString(MaxFlow(source, target));

}

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

clear();

}

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

{

int q;

if (!Int32::TryParse(Convert::ToString(dataGridView1->CurrentCell->Value), q))

{

MessageBox::Show("Вводите только числа", "Error");

dataGridView1->CurrentCell->Value = "0";

}

}

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

{

pictureBox1->Image = nullptr;

pictureBox1->Refresh();

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

inti = 0;

unsigned c = 0;

int j, z, x, k = 0;

intu[10];

srand(time(0));

x = 0;

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

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

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

std::vector <int> w(8);

for (int h = 0; h < 8; h++) {

w[h] = h; // инициализация диапозоном от 0 до 8

}

std::random_shuffle(w.begin(), w.end());

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

{

int secret = w[c1];

c = c + 1;

srand(c);

if (secret == 0)

{

a[c1] = 100 + secret * 20;

b[c1] = 100 + secret * 20;

}

if (secret == 1)

{

a[c1] = 220 - secret * 20;

b[c1] = 80 + secret * 20;

}

if (secret == 2)

{

a[c1] = 370 - secret * 10;

b[c1] = 160 - secret * 10;

}

if (secret == 3)

{

a[c1] = 380 - secret * 10;

b[c1] = 230 - secret * 10;

}

if (secret == 4)

{

a[c1] = 380 - secret * 15;

b[c1] = 180 + secret * 15;

}

if (secret == 5)

{

a[c1] = 175 + secret * 5;

b[c1] = 300 - secret * 10;

}

if (secret == 6)

{

a[c1] = 80 + secret * 10;

b[c1] = 100 + secret * 15;

}

if (secret == 7)

{

a[c1] = 240 - secret * 20;

b[c1] = 150 - secret * 5;

}

}

int counter = 0;

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

{

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

{

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

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

Brush^ Кисть = gcnewSolidBrush(Color::Black);

Brush^ неКисть = gcnewSolidBrush(Color::Blue);

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

{

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

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

}

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::Red, a[j] - 2, b[j] - 2, 8, 8);

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

{

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

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

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

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

}

}

}

counter += 1;

}

}

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

pictureBox1->Image = nullptr;

pictureBox1->Refresh();

}

};

}

Файл «Header.h»

#pragma once

#include "conio.h"

#include "stdlib.h"

#include <stdio.h>

#include <tchar.h>

#include <cstdlib>

#include <SDKDDKVer.h>

#include "time.h"

#include "math.h"

#include <iostream>

#include <vector>

#include <algorithm>

#include <ctime>

#define _CRT_SECURE_NO_WARNINGS

Результаты работы

поток транспортный граф программа

Рис.7. Пример работы программы

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

...