首页 > 其他分享 >网络流浅析

网络流浅析

时间:2024-07-25 15:18:58浏览次数:12  
标签:最大 容量 增广 网络 dfs 流量 浅析 rightarrow

网络流

概述

网络(network)是指一个特殊的有向图 \(G=(V,E)\) ,其与一般有向图的不同之处在于有容量和源汇点。

  • \(E\) 中的每条边 \((u, v)\) 都有一个被称为容量(capacity)的权值,记作 \(c(u, v)\)。当 \((u,v)\notin E\) 时,可以假定 \(c(u,v)=0\)。

  • \(V\) 中有两个特殊的点:源点(source)\(s\) 和汇点(sink)\(t\)(\(s \ne t\))。

一条简单增广路上存在一个流量 \(flow\) 指当前增广路上通过的流量,在最大流问题中,这个值则是增广路上所有容量的权值最小值。

  1. 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即 \(0 \leq f(u,v) \leq c(u,v)\)。
  2. 流守恒性:除源汇点外,任意结点 \(u\) 的净流量为 \(0\)。其中,我们定义 \(u\) 的净流量为 \(f(u) = \sum_{x \in V} f(u, x) - \sum_{x \in V} f(x, u)\)。

最大流

最大流是指在图 \(G\) 上选择合适的流量 \(f\)​ ,使得整个网络的流量。

通常大家应该能想到 dfs 去寻找每一条增广路,统计这条增广路的最大流量 \(maxflow\),将这条增广路上所有容量减去 \(maxflow\),表示这条路已经流过了,减去已经流过的流量。

但有时会出现特殊情况:如下图,在 dfs 中,我们会先走 \(u\rightarrow v\) 的路径,这样会使最大流只有1,但实际应该为 \(u\rightarrow q\) 和 \(p\rightarrow v\) 两条流。

flow2.png

所以怎么处理呢,我们发现 \(u\rightarrow v\) 的路径其实只更改了\(u\rightarrow v\) 的容量大小,所以不妨在原图上全建反边,边权容量初始为 \(0\),若有流量经过,在原图\(-=flow\) 时,反图应\(+=flow\)。

这样就可以使最大流不出错。

\(FF(Ford-Fulkerson)增广算法\)

最基础的网络流最大流算法,也是大家最能理解的,通过 dfs 遍历增广路求最大流量,再将这条增广路上的容量减去最大容量,反边加上最大容量,反复操作直至求出答案,复杂度为 \(O(fM)\),\(f\) 为网格的最大流。在此不再详述

\(EK(Edmonds-Karp)算法\)

就是 \(FF\) 的变形,基本思路仍不变,不过是把 dfs 变为时间更少的 bfs 算法,bfs 的优点是层次遍历,不会出现环,节省时间,实现方法与 FF 类同,复杂度为 \(O(NM^2)\)。

\(Dinic算法\)

通过使用 bfs 时进行分层,每层再使用 dfs 去寻找这个层次图 \(G_L\) 的最大增广流 \(f_b\),\(f_b\) 称为 \(G_L\) 的阻塞流。

流程如下:

  1. 在 \(G_f\) 上 BFS 出层次图 \(G_L\)。
  2. 在 \(G_L\) 上 DFS 出阻塞流 \(f_b\)。
  3. 将 \(f_b\)并到原先的流 \(f\) 中,即 \(f \leftarrow f + f_b\)。
  4. 重复以上过程直到不存在从 \(s\) 到 \(t\)​ 的路径。

此时的 \(f\) 即为最大流。

当前弧优化

如果某一时刻我们已经知道了边 \((u,v)\) 已经增广到极限,即边 \((u,v)\) 已无剩余容量或 \(v\) 的后侧已增广至阻塞,则 \(v\) 的流量没有必要再尝试流向出边 \((u,v)\) 。据此,我们对于每个节点 \(u\),我们维护 \(u\) 的出边表中第一条边为还有必要尝试的出边,我们称这个维护指针为当前弧。

通过这种优化,Dinic 算法时间复杂度为 \(O(N^2M)\) 。

标签:最大,容量,增广,网络,dfs,流量,浅析,rightarrow
From: https://www.cnblogs.com/lizihan00787/p/18323216

相关文章

  • 信息收集:网络空间测绘FOFA,查询语法最全使用方法(图文解析)
    前言经小绿书粉丝投稿,特意搜集了一些fofa的使用教程和一些高级用法什么是FOFA?官网描述:FOFA-网络空间资产搜索引擎是华顺信安推出的一款通过对全球网络对外开放服务的资产进行主动或被动方式探测、抓取、存储,分析整理不同种类的网络空间资产指纹信息(规则),并对符合规则的资产......
  • 0基础成功转行网络安全工程师,年薪30W+,经验总结都在这(建议收藏)
    我曾经是一名普通的销售人员,工作了三年,每天重复着相同的工作内容,感觉自己的职业生涯停滞不前,毫无发展前景。我开始思考,如何才能让自己的职业生涯更有意义,更具有挑战性。经过一番调研,我决定转行网络安全工程师。工作了越久,越觉得当初转行网络安全的决定还是非常正确的。目......
  • 转行网络安全,应该选哪个方向?(非常详细)零基础入门到精通,收藏这一篇就够了
    随着互联网技术的快速发展和广泛应用,网络安全形势日益严峻,各种网络攻击和安全威胁不断涌现,给个人、企业乃至国家带来了巨大的风险。为了应对网络风险,网络安全越来越被重视,开始成为入行互联网的备选岗位。网络安全方向众多,涉及到网络安全生命全周期,方向多达几十种。网络安......
  • Springboot网络安全宣传小程序 毕业设计源码70468
                         摘 要随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,网络安全宣传小程序被用户普遍使用,为方便用户能够......
  • eve-NG网络环境模拟神器
    一个看着很像计网实验的一个万能模拟工具。下载https://www.eve-ng.net/index.php/download/安装导入eve镜像之前需要安装一些软件。SecureCRT:用来连接telnet的MobaXterm:类似xshell的工具EVE-NG-Win-Client-Pack-2.0:主要是用于Wireshark抓包直接去官网下载即可https://e......
  • 【网络流】-初识(最大流)
    @目录基础信息引入一些概念基本性质最大流定义Ford–Fulkerson增广Edmons−Karp算法Dinic算法参考文献基础信息引入假定现在有一个无限放水的自来水厂和一个无限收水的小区,他们之间有多条水管和一些节点构成。每一条水管有三个属性:流向,流量,容量。我们用\((u,v)\)表示一条......
  • 没发论文的注意啦!重磅更新!GWO-BP-AdaBoost预测!灰狼优化、人工神经网络与AdaBoost集成
      ......
  • Python网络爬虫详解:实战豆瓣电影信息采集
    文章目录前言一、爬虫是什么?二、常用库及其作用1.Requests2.BeautifulSoup3.lxml4.Scrapy5.Selenium6.PyQuery7.Pandas8.JSON9.Time三、实现步骤步骤一:环境准备步骤二:数据采集步骤三:数据处理步骤四:数据存储总结前言随着互联网的迅猛发展和数据分析需求的不......
  • Linux网络-配置IP
    作者介绍:简历上没有一个精通的运维工程师。希望大家多多关注作者,下面的思维导图也是预计更新的内容和当前进度(不定时更新)。本来IP配置应该放在Linux安装完成的就要配置的,但是由于那个时候对Linux不怎么熟悉,所以单独列了一个章节来讲解。Linux服务器作为一个常用的网络服务......
  • 计算机网络04——子网划分
    IP地址分类地址每一小段最大255,总范围为0.0.0.0——255.255.255.255.255IP地址总分为ABCDE五类 B类:本地环网地址,IP地址变化后,也能发回给自己子网掩码默认子网掩码是固定的,计算出网络地址(对外ip地址)网络地址——由ip地址和子网掩码按位与计算出来的同一子网内的所有i......