福特富尔克森算法
Ford-Fulkerson算法用于检测给定图中从起始顶点到汇顶点的最大流量。在这个图中,每条边都有容量。提供了两个名为Source和Sink的顶点。源顶点全是外边,没有内边,而汇点全是内边,没有外边。
有一些限制:
边上的流量不超过该图的给定容量。
除了源和汇之外,每条边的流入和流出也是相等的。
输入和输出
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: 最大流量为: 19
算法
bfs(vert,start,sink)
输入: 顶点列表、起始节点和汇节点。
输出- 访问接收器时为真。
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#include #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 que; for(i = 0; 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 输出结果 最大流量为: 19