数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究福特-福尔克森算法
福特-福尔克森算法用于检测给定图中从起始点到汇聚点的最大流量。在这个图中，每条边都有容量。提供两个名为源点和汇聚点的点。源点具有所有流出边，无流入边，而汇聚点具有所有流入边，无流出边。
有一些限制
- 一条边上的流量不超过该图的给定容量。
- 对于除源点和汇聚点之外的所有边，进流和出流也将相等。
输入和输出
Input: The adjacency matrix: 0 10 0 10 0 0 0 0 4 2 8 0 0 0 0 0 0 10 0 0 0 0 9 0 0 0 6 0 0 10 0 0 0 0 0 0 Output: Maximum flow is: 19
算法
bfs(vert, start, sink)
输入： 顶点列表、开始节点和汇聚节点。
输出 − 当访问汇聚点时为 True。
Begin initially mark all nodes as unvisited state of start as visited predecessor of start node is φ insert start into the queue qu while qu is not empty, do delete element from queue and set to vertex u for all vertices i, in the residual graph, do if u and i are connected, and i is unvisited, then add vertex i into the queue predecessor of i is u mark i as visited done done return true if state of sink vertex is visited End
fordFulkerson(vert, source, sink)
输入：顶点列表、源点和汇聚点。
输出 − 从开始到汇聚的最大流量。
Begin create a residual graph and copy given graph into it while bfs(vert, source, sink) is true, do pathFlow := ∞ v := sink vertex while v ≠ start vertex, do u := predecessor of v pathFlow := minimum of pathFlow and residualGraph[u, v] v := predecessor of v done v := sink vertex while v ≠ start vertex, do u := predecessor of v residualGraph[u,v] := residualGraph[u,v] – pathFlow residualGraph[v,u] := residualGraph[v,u] – pathFlow v := predecessor of v done maFlow := maxFlow + pathFlow done return maxFlow End
示例
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
typedef struct node {
int val;
int state; //status
int pred; //predecessor
}node;
int minimum(int a, int b) {
return (a<b)?a:b;
}
int resGraph[NODE][NODE];
/* int graph[NODE][NODE] = {
{0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
}; */
int graph[NODE][NODE] = {
{0, 10, 0, 10, 0, 0},
{0, 0, 4, 2, 8, 0},
{0, 0, 0, 0, 0, 10},
{0, 0, 0, 0, 9, 0},
{0, 0, 6, 0, 0, 10},
{0, 0, 0, 0, 0, 0}
};
int bfs(node *vert, node start, node sink) {
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++) {
vert[i].state = 0; //not visited
}
vert[start.val].state = 1; //visited
vert[start.val].pred = -1; //no parent node
que.push(start); //insert starting node
while(!que.empty()) {
//delete from queue and print
u = que.front();
que.pop();
for(i = 0; i<NODE; i++) {
if(resGraph[u.val][i] > 0 && vert[i].state == 0) {
que.push(vert[i]);
vert[i].pred = u.val;
vert[i].state = 1;
}
}
}
return (vert[sink.val].state == 1);
}
int fordFulkerson(node *vert, node source, node sink) {
int maxFlow = 0;
int u, v;
for(int i = 0; i<NODE; i++) {
for(int j = 0; j<NODE; j++) {
resGraph[i][j] = graph[i][j]; //initially residual graph is main graph
}
}
while(bfs(vert, source, sink)) { //find augmented path using bfs algorithm
int pathFlow = 999;//as infinity
for(v = sink.val; v != source.val; v=vert[v].pred) {
u = vert[v].pred;
pathFlow = minimum(pathFlow, resGraph[u][v]);
}
for(v = sink.val; v != source.val; v=vert[v].pred) {
u = vert[v].pred;
resGraph[u][v] -= pathFlow; //update residual capacity of edges
resGraph[v][u] += pathFlow; //update residual capacity of reverse edges
}
maxFlow += pathFlow;
}
return maxFlow; //the overall max flow
}
int main() {
node vertices[NODE];
node source, sink;
for(int i = 0; i<NODE; i++) {
vertices[i].val = i;
}
source.val = 0;
sink.val = 5;
int maxFlow = fordFulkerson(vertices, source, sink);
cout << "Maximum flow is: " << maxFlow << endl;
}输出
Maximum flow is: 19
更新于： 16-Jun-2020
4K+ 浏览
广告