数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程序
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时装研究
法律研究Edmonds-Karp 算法实现 C++ 程序
这是一个用来实现 Edmonds-Karp 算法的 C++ 程序，用于计算源点和汇点之间的最大流量。
算法
Begin function edmondsKarp() : initiate flow as 0. If there is an augmenting path from source to sink, add the path to flow. Return flow. End
示例代码
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int c[10][10];
int flowPassed[10][10];
vector<int> g[10];
int parList[10];
int currentPathC[10];
int bfs(int sNode, int eNode)//breadth first search
{
memset(parList, -1, sizeof(parList));
memset(currentPathC, 0, sizeof(currentPathC));
queue<int> q;//declare queue vector
q.push(sNode);
parList[sNode] = -1;//initialize parlist’s source node
currentPathC[sNode] = 999;//initialize currentpath’s source node
while(!q.empty())// if q is not empty
{
int currNode = q.front();
q.pop();
for(int i=0; i<g[currNode].size(); i++)
{
int to = g[currNode][i];
if(parList[to] == -1)
{
if(c[currNode][to] - flowPassed[currNode][to] > 0)
{
parList[to] = currNode;
currentPathC[to] = min(currentPathC[currNode],
c[currNode][to] - flowPassed[currNode][to]);
if(to == eNode)
{
return currentPathC[eNode];
}
q.push(to);
}
}
}
}
return 0;
}
int edmondsKarp(int sNode, int eNode)
{
int maxFlow = 0;
while(true)
{
int flow = bfs(sNode, eNode);
if (flow == 0)
{
break;
}
maxFlow += flow;
int currNode = eNode;
while(currNode != sNode)
{
int prevNode = parList[currNode];
flowPassed[prevNode][currNode] += flow;
flowPassed[currNode][prevNode] -= flow;
currNode = prevNode;
}
}
return maxFlow;
}
int main()
{
int nodCount, edCount;
cout<<"enter the number of nodes and edges\n";
cin>>nodCount>>edCount;
int source, sink;
cout<<"enter the source and sink\n";
cin>>source>>sink;
for(int ed = 0; ed < edCount; ed++)
{
cout<<"enter the start and end vertex along with capacity\n";
int from, to, cap;
cin>>from>>to>>cap;
c[from][to] = cap;
g[from].push_back(to);
g[to].push_back(from);
}
int maxFlow = edmondsKarp(source, sink);
cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;
}输出
enter the number of nodes and edges 6 7 enter the source and sink 0 4 enter the start and end vertex along with capacity 0 1 14 enter the start and end vertex along with capacity 2 4 10 enter the start and end vertex along with capacity 6 7 9 enter the start and end vertex along with capacity 5 2 10 enter the start and end vertex along with capacity 1 4 12 enter the start and end vertex along with capacity 2 0 15 enter the start and end vertex along with capacity 5 3 15 Max Flow is:12
更新于： 30-Jul-2019
3K+ 次查看
广告