package org.xiu68.exp.exp10; import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays; public class Exp10_2 {
//实现Ford-Fulkerson算法，求出给定图中从源点s到汇点t的最大流，并输出最小割。
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] c=new int[][]{
{0,1,1,0},
{0,0,1,1},
{0,0,0,1},
{0,0,0,0}
};
MGraph1 m1=new MGraph1(c);
m1.fordFulkerson(0, 3); int[][] c1=new int[][]{
{0,3,3,4,0,0,0},
{0,0,0,0,2,0,0},
{0,1,0,0,1,0,0},
{0,0,0,0,0,5,0},
{0,0,0,1,0,1,2},
{0,0,0,0,0,0,5},
{0,0,0,0,0,0,0}
};
MGraph1 m2=new MGraph1(c1);
m2.fordFulkerson(0, 6);
}
} class MGraph1{
private int[][] c; //容量矩阵
private int[][] e; //残量矩阵
private int[][] f; //当前流矩阵
private int vexNum; //顶点数量 public MGraph1(int[][] c){
this.c=c;
this.vexNum=c.length;
this.e=new int[vexNum][vexNum];
this.f=new int[vexNum][vexNum]; //刚开始时残量矩阵等于容量矩阵
for(int i=0;i<vexNum;i++){
System.arraycopy(c[i], 0, e[i], 0, c[i].length);
} }
//fordFulkerson算法
public void fordFulkerson(int s,int t){
int[] route=new int[vexNum]; //s到t的路径数组,route[i]表示i的前一个顶点 while(bfs(s,t,route)){ //若还能找到一条路径 //寻找路径中流最小的边的大小(在残量矩阵中)
int min=Integer.MAX_VALUE;
int tail=t;
int head=route[t]; while(head!=-1){
if(e[head][tail]<min){
min=e[head][tail];
}
tail=head;
head=route[head];
} //更新当前流矩阵和残量矩阵
int tail1=t;
int head1=route[tail1];
while(head1!=-1){
//更新当前流矩阵
if(c[head1][tail1]!=0){
f[head1][tail1]+=min; //容量矩阵中存在边,增加head1到tail1的流的大小为min
}else{
f[head1][tail1]-=min; //容量矩阵中不存在边，撤销head1到tail1的流的大小为min
}
//更新残量矩阵
e[head1][tail1]-=min; //head1到tail1的流量减少min
e[tail1][head1]+=min; //tail1到head1的流量增加min tail1=head1;
head1=route[head1];
}//while
//route=new int[vexNum];
Arrays.fill(route, 0); //初始化路径数组
}//while 还能找到一条s到t的路径 int maxFlow=0;
for(int i=0;i<vexNum;i++) //最大流为 当前流矩阵中 从s流出的量
maxFlow+=f[s][i];
System.out.println("最大流为:"+maxFlow); System.out.print("最小割为(集合S)：");
ArrayList<Integer> cut=cut(s);
for(int i=0;i<cut.size();i++)
System.out.print(cut.get(i)+" ");
System.out.println(); } //广度优先搜索在残量图e中寻找s到t的路径
public boolean bfs(int s,int t,int[] route){
boolean[] visited=new boolean[vexNum]; //访问数组
visited[s]=true; ArrayDeque<Integer> queue=new ArrayDeque<>();
route[s]=-1; //设s的前一个顶点为-1 for(int i=0;i<vexNum;i++){
if(e[s][i]!=0 && !visited[i]){ //在残量矩阵中s到i存在一条路径
queue.add(i);
route[i]=s;
visited[i]=true;
}
} while(!queue.isEmpty()){
int middleVex=queue.poll();
if(middleVex==t){
return true;
}else{
for(int i=0;i<vexNum;i++){
if(e[middleVex][i]!=0 && !visited[i]){
queue.add(i);
route[i]=middleVex;
visited[i]=true;
}
}
}
}//while
return false;
} //求最小割
//在残量矩阵中,从s开始做一次搜索,从s能达到的所有的顶点都属于集合S
public ArrayList<Integer> cut(int s){
boolean[] visited=new boolean[vexNum];
ArrayList<Integer> cut=new ArrayList<>(); //保存最小割,集合S
dfs(visited,cut,s);
return cut;
}
//深度优先搜索
private void dfs(boolean[] visited,ArrayList<Integer> cut,int v){
cut.add(v);
visited[v]=true;
for(int i=0;i<vexNum;i++){
if(e[v][i]!=0 && !visited[i]){
dfs(visited,cut,i);
}
}
}
}