【大数据分析】FordFulkerson算法（JAVA实现）
（1）点连通度，一个图G至少要去掉多少个点会变成非连通图或者平凡图（连通图，任意两点之间至少存在一条路径）。（2）边连通度，一个图G至少要去掉多少条边才能变成非连通图。
定义
点连通度和边连通度
（1）点连通度，一个图G至少要去掉多少个点会变成非连通图或者平凡图（连通图，任意两点之间至少存在一条路径）。
（2）边连通度，一个图G至少要去掉多少条边才能变成非连通图。
流网络
流网络（Flow Network），指一类特殊的加权有向的复杂网络（图）。其中有向性可以用于表示能量、物质、货币、信息、注意力等流动的方向。流量是两个节点之间的边的权重。流网络有两个特殊的节点，源和汇（用source和sink代替）。所谓流，即一条从S出发，经过若干节点之后，最终到达T的路径。
假设有一个流网络图G如下所示：
注意每一条边上的流量信息表示：（ f c u r r e n t ( u , v ) f_{current}(u,v) fcurrent(u,v)/ f m a x ( u , v ) f_{max}(u,v) fmax(u,v)），其中 f c u r r e n t ( u , v ) f_{current}(u,v) fcurrent(u,v)表示当前经过 u u u， v v v之间边的流量， f m a x ( u , v ) f_{max}(u,v) fmax(u,v)表示 u u u， v v v之间边所能承载的最大流量，并且 f c u r r e n t ( u , v ) < f m a x ( u , v ) f_{current}(u,v)<f_{max}(u,v) fcurrent(u,v)<fmax(u,v)
根据上图G的流量信息，大致的流路径如下图所示，分别是蓝色箭头组成的流，以及红色和绿色，此时我们可以称：从S到T的流量为3。
（图 1）
但是对于整个图而言，从S到T所能承载的最大流量并不是3，而是4，如下图所示，分别是红，绿，橙，粉。相比上图可知，为了求出该图的最大流量承载量，蓝色流由于占用了关键的边，在下图中被抛弃，而多出两条新的路径（紫色和橙色），而这两条流都部分占用了原本蓝色流的边。
（图 2）
流网络的割
（图 3）
定义：
（1）假设有一个流网络 G ( V , E ) G(V,E) G(V,E)，所谓割， 将 V V V 划分为 S S S 和 T = V − S T=V-S T=V−S 两部分，使得 s ∈ S s \in S s∈S ， t ∈ T t \in T t∈T。图3中的割为 ( S , T ) (S,T) (S,T)，
（2）割 ( S , T ) (S,T) (S,T) 的容量。指从集合 S S S到集合 T T T的所有有向边的的容量之和（不算反方向，必须是 S − > T S->T S−>T）。例如上图中割的容量是 c ( u , w ) + c ( v , x ) = 26 c(u,w)+c(v,x)=26 c(u,w)+c(v,x)=26
（3）流过割的净流量。如果 f f f 是流，则穿过割 ( S , T ) (S,T) (S,T) 的净流量被定义为 f ( S , T ) f(S,T) f(S,T)（包括反向的， S − > T S->T S−>T为正， T − > S T->S T−>S为负）。如上图所示，当前该流网络穿过割的净流量为 f ( u , w ) + f ( v , x ) − f ( w , v ) = 12 + 11 − 4 = 19 f(u,w)+f(v,x)-f(w,v)=12+11-4=19 f(u,w)+f(v,x)−f(w,v)=12+11−4=19
残留网络
假设有一个流网络G，基于现有的流情况 f c u r r e n t f_{current} fcurrent，其还可以容纳的流所组成的网络。例如，假设现有的流网络以及流的情况如下图所示：
（图 4）
其对应的残留网络为：
（图 5）
由上面两张图可以看出，从原流网络到残留网络的过程实际上需要考虑正向和反向，不管这个反向对于两个而言是否在原流网络中已经存在。
（例如：绿色标识的正反方向在原流网络中已经存在，而红色标识的反方向在原流网络中是没有的）
残留网络中每一条边的残留流量的计算步骤如下：
（1）先构建所有边的反方向（特指红色，绿色代表已经存在，不需要构建）。
（2）针对每一条边（包括正，反方向），计算 f m a x − f c u r r e n t + f ( o p p o s i t e , c u r r e n t ) f_{max} - f_{current}+f_{(opposite,current)} fmax−fcurrent+f(opposite,current)作为残留网络的残留量 ，其中， f ( o p p o s i t e , c u r r e n t ) f_{(opposite,current)} f(opposite,current)是该边的反向边当前所承载的流量。如果该边是新构建的边（红色）的话，那么它的 ( f c u r r e n t / f m a x ) (f_{current}/f_{{max}}) (fcurrent/fmax)为 ( 0 / 0 ) (0/0) (0/0)。
增广路径
增广路径是一个图根据它的残留网络得到的一条简单路径，这条路径的意义在于体现整个网络基于这条路径还能增加多少流量，例如： s − > v − > w − > t s->v->w->t s−>v−>w−>t，如果向这条路径增加流量，可以为这个网络的流值增加4。
如果我们使用同样的方法寻找增广路径，直到找不到为止，这是我们就得到一个拥有最大网络流的流网络图。
证：当G的残留网络中无法找到增广路径时，f是G的最大流
如下图所示，定义 S S S是节点 s s s有通路到达的点的集合（这个通路是增广路径），显然 t ∉ S t\notin S t∈/S，因为 s s s到 t t t没有通路，这是，我们令 T = V − S T=V-S T=V−S。那么 ( S , T ) (S,T) (S,T)就是一个割。如下图所示：
进一步，对于节点 i ∈ S i\in S i∈S， j ∈ T j\in T j∈T，有 f ( i , j ) = c ( i , j ) f(i,j)=c(i,j) f(i,j)=c(i,j)。如果 f ( i , j ) < c ( i , j ) f(i,j)<c(i,j) f(i,j)<c(i,j)，这说明节点 i i i和节点 j j j之间依然存在通路，则 j ∈ S j\in S j∈S，而这与 j ∈ T j\in T j∈T矛盾。
因此当前流 f f f等于当前的割的容量， f f f就是最大流。
FordFulkerson算法
算法大致步骤说明
FordFulkerson算法总体上的步骤如下：
（1）更新（初始化）当前网络。根据增广路径更新当前图。
（2）构造残留网络。根据当前网络情况构造残留网络。
（3）找到增广路径。根据残留网络找到一条增广路径。
重复（1），（2），（3）。
完整代码如下
详细代码可参考：https://www.cnblogs.com/DarrenChan/p/9563511.html
Main：算法主方法
package com.edata.graph.FordFulkerson;
public class Main {
public static void main(String[] args) {
test2();
}
private static void test(){
Graph graph = new Graph(6);
Edge[] edges = new Edge[9];
edges[0] = new Edge(0,1,0,16);
edges[1] = new Edge(0,2,0,13);
edges[2] = new Edge(1,3,0,12);
edges[3] = new Edge(2,1,0,4);
edges[4] = new Edge(2,4,0,14);
edges[5] = new Edge(3,2,0,9);
edges[6] = new Edge(3,5,0,20);
edges[7] = new Edge(4,3,0,7);
edges[8] = new Edge(4,5,0,4);
for(int i = 0;i<9;i++)
graph.insertEdge(edges[i]);
graph.MaxFlow();
graph.showResult();
}
public static void test2(){
Graph graph = new Graph(6);
Edge[] edges = new Edge[9];
edges[0] = new Edge(0,1,4,16);
edges[1] = new Edge(0,2,0,13);
edges[2] = new Edge(1,3,4,12);
edges[3] = new Edge(2,1,0,4);
edges[4] = new Edge(2,4,4,14);
edges[5] = new Edge(3,2,4,9);
edges[6] = new Edge(3,5,0,20);
edges[7] = new Edge(4,3,0,7);
edges[8] = new Edge(4,5,4,4);
for(int i = 0;i<9;i++)
graph.insertEdge(edges[i]);
graph.bianli();
graph.MaxFlow();
graph.showResult();
graph.bianli();
}
}
Edge
package com.edata.graph.FordFulkerson;
/**
* 网络中的边
*/
public class Edge {
private int v1;
private int v2;
private int capacity;
private int flow;
public Edge(int v1,int v2,int flow,int capacity){
this.v1 = v1;
this.v2 = v2;
this.capacity = capacity;
this.flow = flow;
}
public int getV1(){
return v1;
}
public int getV2(){
return v2;
}
public int getCapacity(){
return capacity;
}
public int getFlow(){
return flow;
}
public void setFlow(int f){
flow = f;
}
}
Edge2
package com.edata.graph.FordFulkerson;
/**
* 残存网络中的边
*/
public class Edge2 {
private int v1;
private int v2;
private int flow;
public Edge2(int v1,int v2,int flow){
this.v1 = v1;
this.v2 = v2;
this.flow = flow;
}
public int getV1(){
return v1;
}
public int getV2(){
return v2;
}
public int getFlow(){
return flow;
}
public void setFlow(int f){
flow = f;
}
}
Gf：残留网络
package com.edata.graph.FordFulkerson;
import java.util.LinkedList;
import java.util.Queue;
public class Gf {
private int vNum;
private int eNum;
private LinkedList<Edge2>[] GLists;
public Gf(int n){
vNum = n;
eNum = 0;
GLists = new LinkedList[n];
for(int i = 0;i<n;i++)
GLists[i] = new LinkedList<>();
}
public void insertEdge(Edge2 e){
int v1 = e.getV1();
GLists[v1].add(e);
eNum++;
}
/**
* 返回一条增广路径
* @return
*/
public LinkedList<Integer> augmentingPath(){
LinkedList<Integer> list = new LinkedList<>();
Queue<Integer> queue = new LinkedList<>();
int[] reached = new int[vNum];
int[] preNode = new int[vNum];
for(int i = 0;i<vNum;i++){
reached[i] = 0;
preNode[i] = -1;
}
preNode[0] = -1;
reached[0] = 1;
queue.add(0);
while(!queue.isEmpty()){//没有循环起来
int now = queue.poll();
LinkedList<Edge2> inlist = (LinkedList<Edge2>) GLists[now].clone();
while(!inlist.isEmpty()){
Edge2 e = inlist.pop();
int v2 = e.getV2();
if(reached[v2]==0){
queue.add(v2);
reached[v2] = 1;
preNode[v2] = now;
}
}
}
for(int i = 0;i<vNum;i++){
System.out.println(reached[i]+" "+preNode[i]);
}
if(reached[vNum-1]==0){
//System.out.println("here");
return list;
}
int pointnum = vNum-1;
while(pointnum!=-1){
list.add(0, pointnum);
pointnum = preNode[pointnum];
}
return list;
}
/**
* 根据增广路径得到需要调整的值
* 找到增广路径中最小的边
* @param list
* @return
*/
public int changeNum(LinkedList<Integer> list){
if(list.equals(null))
return 0;
int minchange = 1000;
int v1 = 0;
for(int i = 1;i<list.size();i++){
int v2 = list.get(i);
LinkedList<Edge2> elist = (LinkedList<Edge2>) GLists[v1].clone();
Edge2 edge = elist.pop();
while(edge.getV2()!=v2){
edge = elist.pop();
}
if(minchange>edge.getFlow())
minchange = edge.getFlow();
v1 = v2;
}
return minchange;
}
public void bianli(){
System.out.println("残存网络 共 "+vNum+" 个顶点， "+eNum+" 条边");
for(int i = 0;i<vNum;i++){
if(GLists[i].size()==0){
System.out.println(i+"没有后继");
continue;
}
for(int j = 0;j<GLists[i].size();j++){
Edge2 e = GLists[i].get(j);
System.out.println("[ "+e.getV1()+" , "+e.getV2()+" , "+e.getFlow()+" ]");
}
}
}
}
Graph：当前流网络类
package com.edata.graph.FordFulkerson;
import java.util.LinkedList;
public class Graph {
private int vNum;
private int eNum;
private Gf gf;
private LinkedList<Edge>[] GLists;
public Graph(int n){
vNum = n;
eNum = 0;
GLists = new LinkedList[n];
for(int i = 0;i<n;i++)
GLists[i] = new LinkedList<>();
}
public void insertEdge(Edge e){
int v1 = e.getV1();
GLists[v1].add(e);
eNum++;
}
public void produceGf(){
gf = new Gf(vNum);
for(int i = 0;i<vNum;i++){
LinkedList<Edge> list = (LinkedList<Edge>) GLists[i].clone();
while(!list.isEmpty()){
Edge edge = list.pop();
int v1 = edge.getV1();
int v2 = edge.getV2();
int flow = edge.getFlow();
int capacity = edge.getCapacity();
if(flow==0){
gf.insertEdge(new Edge2(v1,v2,capacity));
}else{
if(flow==capacity){
gf.insertEdge(new Edge2(v2,v1,capacity));
}else if(flow<capacity){
gf.insertEdge(new Edge2(v1,v2,capacity-flow));
gf.insertEdge(new Edge2(v2,v1,flow));
}
}
}
}
}
public Gf getGf(){
return gf;
}
private LinkedList<Integer> augmentingPath(){
return gf.augmentingPath();
}
private int changeNum(LinkedList<Integer> list){
return gf.changeNum(list);
}
/**
* 最大流
*/
public void MaxFlow(){
produceGf();
gf.bianli();
LinkedList<Integer> list = augmentingPath();
while(list.size()>0){
int changenum = changeNum(list);
LinkedList<Integer> copylist = (LinkedList<Integer>) list.clone();//调试
System.out.println("list:");
while(!copylist.isEmpty()){
System.out.print(copylist.pop()+" ");
}
System.out.println();
System.out.println("changenum: "+changenum);
int v1 = 0;
for(int i = 1;i<list.size();i++){
int v2 = list.get(i);
if(!GLists[v1].isEmpty()){
int j = 0;
Edge e = GLists[v1].get(j);
while(e.getV2()!=v2 && j<GLists[v1].size()){
e = GLists[v1].get(j);
j++;
}
if(e.getV2()!=v2 && j==GLists[v1].size()){//调试
j = 0;
e = GLists[v2].get(j);
while(e.getV2()!=v1 && j<GLists[v2].size()){
e = GLists[v2].get(j);
j++;
}
}
e.setFlow(e.getFlow()+changenum);
}
v1 = v2;
}
bianli();
produceGf();
gf.bianli();
list = augmentingPath();
}
}
public void bianli(){
System.out.println("共有 "+vNum+" 个顶点， "+eNum+" 条边");
for(int i = 0;i<vNum;i++){
if(GLists[i].size()==0)
continue;
for(int j = 0;j<GLists[i].size();j++){
Edge e = GLists[i].get(j);
System.out.println("[ "+e.getV1()+" , "+e.getV2()+" , "+e.getFlow()+" , "+e.getCapacity()+" ]");
}
}
}
public void showResult(){
bianli();
int maxflow = 0;
for(int i = 0;i<vNum;i++){
if(GLists[i].size()>0){
for(int j = 0;j<GLists[i].size();j++){
if(GLists[i].get(j).getV2() == vNum-1){
maxflow += GLists[i].get(j).getFlow();
}
}
}
}
System.out.println("最大流为 "+maxflow);
}
}
永洪科技，致力于打造全球领先的数据技术厂商，具备从数据应用方案咨询、BI、AIGC智能分析、数字孪生、数据资产、数据治理、数据实施的端到端大数据价值服务能力。
更多推荐
0
0- 0
已为社区贡献11条内容
所有评论(0)