Edmonds-Karp算法(EK算法)简单讲解及实现(邻接表)

时间:2024-10-02 15:56:15

目录

  • 最大流问题介绍
    • 图定义
    • 源点与汇点
    • 最大流问题描述
  • Ford-Fulkerson方法
    • 回退边与增广图
    • 伪代码
    • 图解
  • Edmonds-Karp算法
    • 复杂度
    • 代码实现细节
    • 代码

最大流问题介绍

图定义

给定一张有向图,a->b 边的权值表示当前情况下,从a到b能够发送的流量上限是多少,比如 a->b = 10 表示当前能够从a发10流量给b,当然我们也可以选择不发那么多。

例子:
假设a->b 之间未有任何流量的发送,此时我们发8流量,那么 a->b = 10 变为 a->b = 2a->b 能够发送的流量上限由10 变为 2

源点与汇点

源点只发不收,汇点只收不发,其他点作为中转站,既可以发也可以收,这像极了快递物流网络。。。

源点:卖家
汇点:买家
其他点:快递物流站点

最大流问题描述

从源点能够想方设法发送到汇点的最大流量的值,而求解这个问题就是求解这个最大值

你可能会想:这不是直接把源点发送的流量拉满就行了?????

然而事实是这样的:两点之间发送流量最大值取决于两点之间管道最细的地方的大小(木桶原理),前面塞太多后面放不下。。。

Ford-Fulkerson方法

Ford-Fulkerson不是算法,是一种方法,而通过bfs实现这种方法,叫做Edmonds-Karp算法

回退边与增广图

Ford-Fulkerson定义了一个非常具有创造性的“回退边”

如果我们在a->b中塞入x流量,表示我们买了x货物,于是我们可以退货。
回退边描述了这种退货的行为,回退边的权值是我们已经塞入的流量的大小(联系现实生活中,买了x货物,最多退货量为x)

在这里插入图片描述

我们在原图g的基础上增加回退边,构成原图的增广图ga,增广图包含的回退边的权值等于已经塞入的流量的大小

伪代码

Ford-Fulkerson方法提供了一种求解最大流的思路,是一个很巧妙的贪心思路,这是他的伪代码:

sum = 0
while True:
	构造原图g的增广图ga
	在增广图ga上找到一条从源点到汇点的最短路径p,这个最短指的是经过的点最少而不是经过的边权值之和最小
	if 找不到p :
		break
	记录p一路走来遇到的"最细"的管道大小f(即经过的所有边中权值的最小值)
	通过f来更新原图中路径p上的边:
	for(a->b) in p:
		(a->b)能够通过的流量上限 -= f
		(b->a)能够通过的流量上限 += f
	sum += f
	
sum就是图最大流
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

很抽象

图解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

Edmonds-Karp算法

EK算法之所以是算法,在于它确定了在增广图上找最短路径的方法,即BFS,因为bfs的特性,b到终点一定是最短路

复杂度

bfs用邻接表,复杂度为O(e),更新边复杂度O(e),而每次最少增长1的流量,假设图最大流答案是f,则最多需要fbfs,所以总复杂度为(O(e)+O(e) * f) = O(ef)

代码实现细节

  1. 因为边具有属性,邻接表adj[x]不再存储下一个顶点的信息,而是存储所有从x出发的边,在边集合中的下标
  2. 一条边具有两个属性:起点,当前允许的最大流量
  3. 因为回退边的存在,总共边的数量是原图边数量的两倍
  4. 在bfs的同时记录路径使用生成树 father[] 数组即可做到,father[x]=-1表示x未被访问
  5. bfs的同时记录最细流量,使用min_flow[]数组,假设有边a->b,那么有 min_flow[b] = min(该边允许的流量最大值, min_flow[a])
  6. bfs返回值为true表示找到,否则没找到路径
  7. 边的权值为0则不可走,因为每次最小压入1流量
  8. bfs的时候,正向边或回退边都可以走,只要权值不为0

代码

ps:如果您在着手实现深圳大学算法课程的实验,请手下留情,不要全部copy,否则代码查重系统将会展现他那残忍无情的精准

#include <bits/stdc++.h>

using namespace std;

typedef struct edge
{
	int st, ed, val;	// 起点, 终点, 还能通过多少流量(其中起点不必要,只是方便打印调试信息)
	edge(){}
	edge(int a, int b, int c){st=a;ed=b;val=c;}	
}edge;

int n,e,src,dst,ans;		// 顶点数, 初始边数, 源, 目, 答案 
vector<vector<int>> adj;	// adj[x][i]表示从x出发的第i条边在边集合中的下标 
vector<edge> edges;			// 边集合 
vector<int> min_flow;		// min_flow[x]表示从起点到x的路径中最细流 
vector<int> father;			// 生成树 

bool bfs_augment()
{
	for(int i=0; i<n; i++) father[i]=-1;
	for(int i=0; i<n; i++) min_flow[i]=1145141919; // inf
	father[src] = src;
	
	queue<int> q; q.push(src);
	while(!q.empty())
	{
		int x=q.front(),y; q.pop();
		if(x==dst) return true;
		for(int i=0; i<adj[x].size(); i++)
		{
			edge e = edges[adj[x][i]];
			y = e.ed;
			if(father[y]!=-1 || e.val==0) continue;
			father[y] = x;
			min_flow[y] = min(e.val, min_flow[x]);
			q.push(y);
		}
	}
	return false;
}

void graph_update()
{
	int x, y=dst, flow=min_flow[dst], i;
	cout<<"更新流量: "<<flow<<" 路径: ";
	ans += flow;
	vector<int> path;
	while(y!=src)	// 沿着生成树找起点并沿途更新边 
	{
		path.push_back(y);
		x = father[y];
		for(i=0; i<adj[x].size(); i++) if(edges[adj[x][i]].ed==y) break;	
		edges[adj[x][i]].val -= flow;
		for(i=0; i<adj[y].size(); i++) if(edges[adj[y][i]].ed==x) break;
		edges[adj[y][i]].val += flow;
		y = x;
	}
	path.push_back(y);
	for(int i=path.size()-1; i>=0; i--) cout<<path[i]<<" "; cout<<endl;
}

int main()
{
	cin>>n>>e>>src>>dst;
	adj.resize(n); 
	father.resize(n); 
	min_flow.resize(n); 
	edges.resize(e*2);
	for(int i=0; i<e; i++)
	{
		int st, ed, limit; cin>>st>>ed>>limit;
		edges[2*i] = edge(st, ed, limit);
		edges[2*i+1] = edge(ed, st, 0);
		adj[st].push_back(2*i); adj[ed].push_back(2*i+1);
	}
	
	while(1)
	{
		if(!bfs_augment()) break;
		graph_update();
		// for(int i=0; i<(); i++) cout<<edges[i].st<<" -> "<<edges[i].ed<<" val="<<edges[i].val<<endl;
	}
	cout<<"最大流:"<<ans<<endl;
	
	return 0;
}

/*
6 7 0 5
0 2 2
0 1 2
1 4 1
2 4 5
2 3 2
3 5 1
4 5 2

7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

*/
  • 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