• 【大数据分析】FordFulkerson算法（JAVA实现）

    定义

    点连通度和边连通度

    （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)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)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();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    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;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    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;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    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()+" ]");
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120

    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);

    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
  • 相关阅读:
    day32多线程02
    防止消息丢失与消息重复——Kafka可靠性分析及优化实践
    2023秋招华为技术岗线上面试经历
    SpringMVC框架学习笔记（四）：模型数据 以及 视图和视图解析器
    telnet测试smtp
    发必收藏的好用API接口，可领取免费次数
    隆云通二氧化硫传感器
    Docker-compose
    【Ubuntu搭建MQTT Broker及面板+发布消息、订阅主题】
    给Hexo添加说说功能
  • 原文地址：https://blog.csdn.net/sword_csdn/article/details/126518562