Java实现最大流量问题

1 问题描述

何为最大流量问题？

给定一个有向图，并为每一个顶点设定编号为0~n，现在求取从顶点0(PS：也可以称为源点)到顶点n(PS:也可以称为汇点)后，顶点n能够接收的最大流量。图中每条边的权值为该边的容量，从顶点0到顶点n的某一条路径中最大流量不能超过该路径中任何一条边剩下的容量。

2 解决方案

上述对于最大流量问题的描述是楼主自己个人描述，描述的有点粗暴简略>~<。

求取最大流量问题的的核心要理解三个概念：

（1）残留网络

（2）增广路径

（3）流网络的割

下图是对于最大流量问题实现的一个图，该图共有7条有向边，从顶点1到顶点6的最大流量为3。

package com.liuzhen.practice;

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

    public static int maxV = Integer.MAX_VALUE;

    public static int[][] capacity = new int[6][6]; //用于统计给定图前向边和后向边剩余流量

    public static int[] flow = new int[6];  //用于统计从源点到图中任意一点i的最大可增加的流量

    public static int[] pre = new int[6];  //用于记录当前到达顶点的前驱顶点

    public int bfs(int[][] graph) {  //使用BFS遍历，寻找给定图的增广路径

        ArrayList<Integer> list = new ArrayList<Integer>();

        list.add(0);      //源点为顶点0

        for(int i = 0;i < 6;i++) {

            pre[i] = -1;   //初始化所有顶点的前驱顶点为-1

        }

        pre[0] = 0;     //源点的前驱顶点设定为自己

        flow[0] = maxV; //源点的前驱顶点到源点的增加流量设定为无穷大

        while(!list.isEmpty()) {

            int index = list.get(0);

            list.remove(0);

            if(index == 5)

                break;

            for(int i = 0;i < graph.length;i++) {

                if(capacity[index][i] > 0 && pre[i] == -1) {//当顶点i未被访问且到达顶点i有剩余流量时

                    pre[i] = index;  //顶点i的前驱顶点为index

                    flow[i] = Math.min(flow[index], capacity[index][i]);

                    list.add(i);

                }

            }

        }

        if(pre[5] != -1)

            return flow[5];

        return -1;

    }

    public void getResult(int[][] graph) {

        int result = 0;

        int temp = bfs(graph);

        while(temp != -1) {

            result = result + temp;

            int start = pre[5];

            int end = 5;

            while(start != 0) {

                capacity[start][end] -= temp;   //前向边剩余流量减少temp

                capacity[end][start] += temp;   //后向边剩余流量增加temp

                end = start;

                start = pre[end];

            }

            capacity[0][end] -= temp;

            capacity[end][0] += temp;

            temp = bfs(graph);

        }

        System.out.println("给定图的最大流量为："+result);

        return;

    }

    public static void main(String[] args) {

        Main test = new Main();

        int[][] graph = new int[6][6];

        Scanner in = new Scanner(System.in);

        int num = in.nextInt();   // 给定图的边数目

        for(int i = 0;i < num;i++) {

            int a = in.nextInt();

            int b = in.nextInt();

            int value = in.nextInt();

            graph[a - 1][b - 1] = value;

            capacity[a - 1][b - 1] = value;//前向边起始剩余流量为边的容量，后向边起始剩余流量为0

        }

        test.getResult(graph);

    }

}

运行结果：

1 2 2

3 4

5 3

3 5

3 1

6 4

2 6

给定图的最大流量为：3

巴特西

Java实现最大流量问题

最新文章

热门文章