当前位置： 首页 > news >正文

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

news 来源：原创 2024/4/29 23:45:57

定义

点连通度和边连通度

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

    }

}

相关文章：

  • Linux ARM平台开发系列讲解（GMSL摄像头篇）1.2 MAX9296 GMSL链路配置
  • 小波神经网络的基本原理,小波神经网络算法原理
  • 摄影测量+元宇宙！虚拟校园还有哪些值得我们期待的？
  • LeetCode_数组_中等_915.分割数组
  • Java泛型中的 “？super T“ 与 “？extends T“ 有何不同
  • MaterialDesign组件
  • 如何在不修改原始数组的情况下反转数组？
  • 以太坊学习二：签名
  • 配置本地Maven仓库——IDEA配置本地Maven源
  • mysql8-索引的使用规则验证
  • Python神经网络入门与实战,神经网络算法python实现
  • un8.31:用jQuery实现调用不同项目api接口的功能。
  • Java Agent入门教程
  • 航班信息查询 易语言代码
  • C++ 小游戏 视频及资料集（四）
  • python3.6+scrapy+mysql 爬虫实战
  • “Material Design”设计规范在 ComponentOne For WinForm 的全新尝试！
  • 【mysql】环境安装、服务启动、密码设置
  • 【剑指offer】让抽象问题具体化
  • k8s 面向应用开发者的基础命令
  • leetcode388. Longest Absolute File Path
  • Python学习之路16-使用API
  • Spring Security中异常上抛机制及对于转型处理的一些感悟
  • SpringCloud（第 039 篇）链接Mysql数据库,通过JpaRepository编写数据库访问
  • SQL 难点解决：记录的引用
  • yii2中session跨域名的问题
  • 从0搭建SpringBoot的HelloWorld -- Java版本
  • 解决iview多表头动态更改列元素发生的错误
  • 名企6年Java程序员的工作总结，写给在迷茫中的你！
  • 前端工程化（Gulp、Webpack）-webpack
  • 前端性能优化--懒加载和预加载
  • 如何合理的规划jvm性能调优
  • 什么软件可以剪辑音乐？
  • 微服务框架lagom
  • 译有关态射的一切
  • (42)STM32——LCD显示屏实验笔记
  • （C语言版）链表（三）——实现双向链表创建、删除、插入、释放内存等简单操作...
  • （二）PySpark3：SparkSQL编程
  • （附源码）python旅游推荐系统 毕业设计 250623
  • （附源码）spring boot儿童教育管理系统 毕业设计 281442
  • （附源码）ssm本科教学合格评估管理系统 毕业设计 180916
  • （论文阅读笔记）Network planning with deep reinforcement learning
  • (免费领源码）Python#MySQL图书馆管理系统071718-计算机毕业设计项目选题推荐
  • （一） springboot详细介绍
  • (一)appium-desktop定位元素原理
  • .jks文件（JAVA KeyStore）
  • .NET core 自定义过滤器 Filter 实现webapi RestFul 统一接口数据返回格式
  • .NET Reactor简单使用教程
  • .NET 应用架构指导 V2 学习笔记（一） 软件架构的关键原则
  • .NET/C# 判断某个类是否是泛型类型或泛型接口的子类型
  • .NET基础篇——反射的奥妙
  • /dev下添加设备节点的方法步骤（通过device_create）
  • @Builder用法
  • @SentinelResource详解
  • @TableLogic注解说明，以及对增删改查的影响