图论-网络流

前言

大家好,祝大家2017年身体健康,万事如意,开年第一篇blog网路流,希望大家指正。

网路流问题介绍

描述

设给定有向图G=(V,E),其边的容量为cvw.(这些容量可以代表通过一个管道的水的流量或者马路上的交通流量) s为发点,t为收点,最大网络流问题是求从s到t可以通过的最大流量。

性质

在既不是发点s,也不是收点t的任意顶点v,总的进入流必须等于总的发出流。

实际应用举例

最大网络流可以解决二分匹配问题.

二分匹配问题定义

找出E的最大子集E`使得没有顶点含在多于一条的边中。

图解说明

生活中二分匹配问题举例

有一组老师,有一些课,以及每位老师有资格教授的课程表,如果每位老师最多只能开设一门课,那么最多可以开设几门课?

如何转换问题

  1. 以老师(例如下图绿色),课程(下图蓝色)为节点。
  2. 以课程列表中的老师与课程关系构建图,并将每条边的权赋值为1
  3. 创建虚拟节点s,t。s到每个老师有一条权为1的边,每个课程有一条权为1到t的边。

如下图所示:该问题实际为从s到t的最大网络流 。

网络流问题算法实现

语言描述

  1. 以Dijkstra算法,求解从s到t的赋权最短路径。
  2. 找到当前最短路径上的最小权,即为当前最大网络流。
  3. 以当前最短路径和当前最大网络流,修改原图为残余图,保存当前最大网络流。
  4. 以残余图继续执行1,2,3步,直到s和t不连通为止。

图例说明最大网络流算法

代码示例

/**
	 * 获取从起点到终点的最大网络流
	 * @param start 起点
	 * @param end   终点
	 * @return 从起点到终点的最大网络流
	 */
	public  Integer getMaxFlow(Vertex start,Vertex end){
		int maxFlow=0;
		while (true) {
			dijkstra(start, end);//找到从起点到终点的最短路径
			if(end.dist==Integer.MAX_VALUE){
				break;
			}
			printPath(end);//打印路径便于观察
			int currentMaxFlow = getCurrentMaxFlow(end);//得到当前路径的最大网络流
			//修建原图
			changeGraphWeightAndSetMaxFlow(end, currentMaxFlow, maxFlowGraph);
			maxFlow+=currentMaxFlow;//记录最大网络流
			//打印当前最大网络流图,以便追踪是否正确
			System.out.println();
			for (Vertex v : maxFlowGraph.values()) {
				System.out.println(v);
			}
		}
		return maxFlow;
	}

1.获取当前最短路径的最大流

	/**
	 * 获取当前最短路径的最大流
	 * @param end 终点
	 * @return 从起点到终点的当前最大流
	 */
private  Integer getCurrentMaxFlow(Vertex end) {
	if (end.getPath() != null) {
		Integer parentcwv = 0;
		if (end.getPath() != null) {
			parentcwv = getCurrentMaxFlow(end.getPath());
		}
		Integer cwv = end.getPath().getAdj().get(end);
			return Math.min(cwv, parentcwv);
		} else {
			return Integer.MAX_VALUE;
		}

	}

2.修改原图为残余图保留当前网络流

	/**
	 * 为网络流图赋值,修剪原图
	 * 如果原图中有一条边修剪后权为0,去掉该边
	 * @param end 终点
	 * @param currentMaxFlow 当前最大流
	 * @param maxFlowGraph 网络流结果图
	 */
public  void changeGraphWeightAndSetMaxFlow(Vertex end, Integer currentMaxFlow, Map<String, Vertex> maxFlowGraph) {
		if (end.getPath() != null) {
			int oldCwv = end.getPath().getAdj().get(end);
			if (oldCwv - currentMaxFlow > 0) {
				end.getPath().getAdj().put(end, oldCwv - currentMaxFlow);
			} else if (oldCwv - currentMaxFlow == 0) {
				end.getPath().getAdj().remove(end);
			}
			String startName=end.getPath().name;
			Integer oldcvw=maxFlowGraph.get(startName).adj.get(maxFlowGraph.get(end.name));
			maxFlowGraph.get(startName).adj.put(maxFlowGraph.get(end.name), oldcvw+currentMaxFlow);
			maxFlowGraph.get(end.name).setPath(maxFlowGraph.get(startName));
			changeGraphWeightAndSetMaxFlow(end.getPath(), currentMaxFlow, maxFlowGraph);
		}
	}

完整代码地址

[码云地]址:单击跳转](https://git.oschina.net/WLjava/DataStructuresAndAlgorithm/blob/master/src/main/java/chapter9/maxflow/MaxWebFlow.java?dir=0&filepath=src%2Fmain%2Fjava%2Fchapter9%2Fmaxflow%2FMaxWebFlow.java&oid=14cc06fb68373aefc0ec65af571112ac8019f81a&sha=2e3d013f5808da536adc100c90d5a246b9562a28)

github地址:单击跳转

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

13720
来自专栏老马说编程

(34) 随机 / 计算机程序的思维逻辑

随机 本节,我们来讨论随机,随机是计算机程序中一个非常常见的需求,比如说: 各种游戏中有大量的随机,比如扑克游戏洗牌 微信抢红包,抢的红包金额是随机的 北京购...

27560
来自专栏算法修养

整数划分总结

整数划分问题: 笼统上说就是将一根整数划分成若干个整数之和的方案数。整数划分很多不同的问法,也有隐晦的问法。比如n个苹果放到m个盘子里,比如n个砖块堆成m个...

35460
来自专栏计算机视觉与深度学习基础

HDU4832

由于水平和竖直相互独立,所以可以分开计数,最后再用组合数算一下,万年老坑long long #include<cstdio> #include<iostream...

215100
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

27040
来自专栏大数据挖掘DT机器学习

python数据分析师面试题选

python数据分析部分 1. 如何利用SciKit包训练一个简单的线性回归模型 利用linear_model.LinearRegression()函数 #...

76060
来自专栏数据结构与算法

2018.7.30考试

题意:给出两棵树,问在两棵树中任意删除一条边后$1$号节点所在集合的元素相同的方案

12750
来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

40190
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

15010
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

教程 OpenGL ES入门教程1-Tutorial01-GLKit OpenGL ES入门教程2-Tutorial02-shader入门 OpenGL E...

36150

扫码关注云+社区

领取腾讯云代金券