最大流算法：Edmonds-Karp

# 一、 算法简介

## 1.1 最大流问题概述

在图论中，最大流问题是求解在一个有向图中从源节点到汇节点的最大流量的问题。最大流问题在很多实际应用中都有广泛的应用，比如网络流量控制、传输问题等。在最大流问题中，图中的边表示流量通道，边上的权重表示该通道的最大流量限制。

## 1.2 Edmonds-Karp算法概述

Edmonds-Karp算法是一种基于增广路径的最大流算法，它通过不断寻找增广路径来更新当前流，并且保证每次找到的增广路径都是最短路径。该算法利用广度优先搜索（BFS）来寻找增广路径，具有较好的时间复杂度和理论保证。

在Edmonds-Karp算法中，首先初始化流为0，并且通过BFS寻找增广路径，然后更新流量，继续寻找下一个增广路径，直到没有增广路径为止。在每次寻找增广路径时，使用BFS能够保证找到的是最短路径，从而提高算法的效率。

下一节将介绍图论的基础知识，为后续的算法实现做准备。
## 二、 图论基础

### 2.1 流网络的定义

在最大流算法中，我们需要了解一些图论的基础概念。首先要引入流网络的概念。

流网络是一种有向图，它由一个源节点和一个汇节点组成。流从源节点流向汇节点，经过其他中间节点，每个边都有一个容量限制，表示通过这条边的最大流量。

在流网络中，每个边的容量必须是非负整数。此外，流网络中没有自环，即一条边的起点不能是终点。同时，流网络中的边是可以反向的，即可以从汇节点流向源节点。

### 2.2 图的表示方法

在计算机中，图可以通过多种方式进行表示。常见的表示方法有邻接矩阵和邻接表。

- 邻接矩阵是一个二维数组，数组的大小为图中节点的个数。其中，数组的第i行第j列的值表示节点i和节点j之间的边的权重或容量。如果没有边相连，则对应位置的值为0。

- 邻接表使用链表的方式来表示图。对于每个节点，我们维护一个链表，链表中的每个节点表示与当前节点相连的边，该节点包含两部分信息：终点和边的权重或容量。

邻接矩阵的表示方法适用于稠密图，因为它需要占用大量的内存空间。而邻接表则适用于稀疏图，因为它节省了内存空间。

在实现最大流算法时，我们可以根据具体的情况选择适合的图的表示方法。对于规模较小的问题，邻接矩阵可能更方便，而对于规模较大的问题，邻接表可能更