Приложение - Нахождение максимального потока в графе

>

Программа написана на языке 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;

}

Похожие статьи




Приложение - Нахождение максимального потока в графе

Предыдущая | Следующая