Приложение - Нахождение максимального потока в графе
>
Программа написана на языке C++ и откомпилирована в Visual Studio 2015.
#include <iostream>
#include <memory. h>
#include <stdio. h>
#include <conio. h>
#include <Windows. h>
Char* rus(char* st)//функция подключения вывода символов на кириллице
{
Char* p = st;
While (*p)
{
If (*p >= 192)
If (*p <= 239)
*p -= 64;
Else
*p -= 16;
P++;
}
Return st;
}
Const int MAX_VERTICES = 40;
Int NUM_VERTICES; // число вершин в графе
Const int infinity = 10000; // условное число обозначающее бесконечность
// f - массив содержащий текушее значение потока// f[i][j] - поток текущий от вершины i к j
Int f[MAX_VERTICES][MAX_VERTICES];
// с - массив содержащий вместимоти ребер,
// т. е. c[i][j] - максимальная величину потока способная течь по ребру (i, j)
Int c[MAX_VERTICES][MAX_VERTICES];
// набор вспомогательных переменных используемых функцией FindPath - обхода в ширину
// Flow - значение потока чарез данную вершину на данном шаге поиска
Int Flow[MAX_VERTICES];
// Link используется для нахождения собственно пути
// Link[i] хранит номер предыдущей вешины на пути i -> исток
Int Link[MAX_VERTICES];
Int Queue[MAX_VERTICES]; // очередь
Int QP, QC; // QP - указатель начала очереди и QC - число эл-тов в очереди
// поск пути по которому возможно пустить поток алгоритмом обхода графа в ширину// функция ищет путь из истока в сток по которому еще можно пустить поток,
// считая вместимость ребера (i, j) равной c[i][j] - f[i][j],
// т. е. после каждой итерации(одна итерация - один поик пути) уменьшаем вместимости ребер,// на величину пущеного потока
Int FindPath(int source, int target) // source - исток, target - сток
{
QP = 0; QC = 1; Queue[0] = source;
Link[target] = -1; // особая метка для стока
Int i;
Int CurVertex;
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 ((c[CurVertex][i] - f[CurVertex][i])>0 &;&; Flow[i] == 0)
{
// если можем, то добавляем i в конец очереди
Queue[QC] = i; QC++;
Link[i] = CurVertex; // указываем, что в i добрались из CurVertex
// и находим значение потока текущее через вершину i
If (c[CurVertex][i] - f[CurVertex][i] < Flow[CurVertex])
Flow[i] = c[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];
}
Return Flow[target]; // Возвращаем значение потока которое мы еще смогли "пустить" по графу
}
// основная функция поиска максимального потока
Int MaxFlow(int source, int target) // source - исток, target - сток
{
// инициализируем переменные:
Memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTICES); // по графу ничего не течет
Int MaxFlow = 0; // начальное значение потока
Int AddFlow;
Do
{
// каждую итерацию ищем какй-либо простой путь из истока в сток
// и какой еще поток мажет быть пущен по этому пути
AddFlow = FindPath(source, target);
MaxFlow += AddFlow;
} while (AddFlow >0);// повторяем цикл пока поток увеличивается
Return MaxFlow;
}
Int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
Printf(rus(" Нахождение максималтного потока в графе "));
Printf(rus(" Алгоритм Форда-Фалкерсона "));
Printf(rus(" Курсовая работа "));
Printf(rus(" Vipolnil : Иксанов С. А. "));
Printf(rus(" URTiSI Екатеринбург 2015г "));
Printf(rus(" Нажминте любую клавишу для продолжения...."));
Getch();
Int source, target;
Printf(rus(" Введите число вершин в графе -->"));
Scanf("%d", &;NUM_VERTICES);
Printf(rus(" Введите значения истока и стока -->"));
Scanf("%d %d", &;source, &;target);
Printf(rus(" Введите матрицу содержащею вместимость ребер: "));
Printf(rus("каждый элемент - вместимость ребра, направленного из вершины с номером его строки к вершине с номером его столбца "));
Int i, j;
For (i = 0; i<NUM_VERTICES; i++)
For (j = 0; j<NUM_VERTICES; j++)
Scanf("%d", &;c[i][j]);
Printf(rus(" максимальный поток равен:"));
Printf("%d", MaxFlow(source, target));
Getch();
Return 0;
}
Похожие статьи
-
Блок-схема программы представлена ниже на рисунке 2. Рисунок 2- Блок-схема работы программы Работа программы С клавиатуры вводятся следующие значения:...
-
Основные понятия теории графов - Нахождение максимального потока в графе
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин "граф" впервые ввел в 1936 году венгерский математик Денеш Кениг....
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
Орграф приращений, Теорема Форда-Фалкерсона - Нахождение максимального потока в графе
Введем для заданной транспортной сети D и допустимого потока в этой сети орграф приращений, имеющий те же вершины, что и сеть D. Каждой дуге транспортной...
-
Введение - Нахождение максимального потока в графе
Актуальность задачи о максимальном потоке постоянно возрастает вместе со строительством трубопроводов, новых дорог, роста пользователей Интернета и любых...
-
Необходимо разработать программу, которая является важным следствием из теоремы Форда-Фалкерсона, по решению задачи о нахождение максимального потока в...
-
Поток в транспортной сети - Нахождение максимального потока в графе
Функция, определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в...
-
Выбор языка программирования - Нахождение максимального потока в графе
Для написания программы мною был выбран язык программирования C++ и компилятор Visual Studio 2015. C++ является языком программирования, знание этого...
-
Разработка алгоритма нахождения входного потока заявок в имитационной модели контрольно-пропускной системы на основе статистических данных В наши дни...
-
Для того, чтобы узнать, на сколько максимум может увеличится ВРП Краснодарского края, не хватает оптимального значения капитала. Для этого построим...
-
Теперь исходя из нашей модели мы можем просчитать оптимальное кол-во трудящихся, которое потребуется для роста экономики: (39) Рассчитаем данные по годам...
-
Нахождение квази-клик за заданный период - Использование квази-клик для анализа графа рынка России
К полученному графу рынка мы можем применить алгоритм поиска максимальной квази-клики в графе. Поэтому, для целей практического применения, возникла...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Построим функцию роста валового регионального продукта: Таблица 11-Данные для функции роста ВРП Год (t) Y (миллион рублей) 1 372930 2 483951 3 648211 4...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G...
-
Поскольку процесс инвестирования, как правило, имеет большую продолжительность в практике анализа эффективности капитальных вложений, обычно приходится...
-
Введение - Использование квази-клик для анализа графа рынка России
Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей,...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
Понятие и применение графа рынка - Использование квази-клик для анализа графа рынка России
Динамика характеристик отражающих тенденцию поведения фондового рынка может быть интересна многим участникам фондовой биржи и, в особенности, инвесторам....
-
Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России
Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска...
-
Заключение - Использование квази-клик для анализа графа рынка России
Данная выпускная работа была посвящена проблеме поиска плотных подграфов в графе. Основные усилия в ней были направлены на разработку алгоритма поиска...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
-
Високотемпературне коксування, Графітація - Піроліз твердих горючих копалин
Високотемпературне коксування (ВТК). При високотемпературному коксуванні кам'яного вугілля виходять наступні продукти: Тверді - кокс різних сортів; Рідкі...
-
Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...
-
Якщо аргумент і функція задані, то для введення графіка треба обрати з меню Графіки (Graphics) Декартовий графік (X-Y Plot) або клавішу @. У документі...
-
Симплекс-метод - Приложение интегрального и дифференциального исчисления к решению прикладных задач
Теория: Другой способ решения задач линейного программирования - симплекс-метод. Он, в отличие от геометрического, является полностью аналитическим, что...
-
Вычисление потока и циркуляции векторного поля
Вычисление потока и циркуляции векторного поля Векторный теорема стокс остроградский Даны векторное поле и плоскость, которая совместно с координатными...
-
Введение - Приложение интегрального и дифференциального исчисления к решению прикладных задач
Целью данной курсовой работы является самостоятельное изучение следующих разделов высшей математики: задачи линейного программирования (симплексный и...
-
Интерполяция является одной из задач Приближения функции. В общем случае сводит более сложную функцию к более простой. Интерполяция - замена одной...
-
Використання концепції ефективного автомобіля для моделювання динаміки транспортних потоків у транспортній мережі міста Постановка проблеми. Однією з...
-
Планиметрические задачи Задача 1.Написать уравнения касательной и нормали к графику функциив данной точке, если: [3]. Решение. Уравнение касательной...
-
Выводы, Литература - Моделирование крупномасштабной транспортной сети предфрактальными графами
В качестве модели карты дорог предлагается использовать предфрактальные графы, которые естественным образом отражают структуру связей при рассмотрении...
-
Моделирование транспортной сети большой размерности с помощью предфрактальных графов позволяет строить эффективные алгоритмы благодаря свойству...
Приложение - Нахождение максимального потока в графе