网络流算法入门与Ford-Fulkerson算法实现

# 1. 网络流算法概述

## 1.1 什么是网络流？
网络流是指在网络中从一个点到另一个点的流量传输情况。网络流算法旨在解决在网络中最大化/最小化流量的问题，以及在满足各种约束条件下找到最优的流量路径。

## 1.2 网络流算法的应用领域
网络流算法在实际应用中有广泛的应用，如最大流问题、二分图匹配、路径规划、资源分配等领域。在计算机网络、物流、电力系统等领域都有着重要的应用价值。

## 1.3 常见的网络流算法
常见的网络流算法包括Ford-Fulkerson算法、Edmonds-Karp算法、Dinic算法等。这些算法在不同场景下有着不同的适用性和效率表现。

# 2. 流网络建模

在网络流算法中，流网络的建模是至关重要的一步。通过合适的节点与边的定义，以及对容量与流量的明确定义，可以准确地描述网络流问题，并为后续算法的实现提供基础。

### 2.1 节点与边的定义

在流网络中，节点通常表示网络中的位置或实体，而边则表示节点之间的连接。节点分为源点（Source）和汇点（Sink），分别对应流网络的起点和终点；边则表示节点之间的路径或关系。在流网络的建模中，通常还会包括普通节点（Intermediate Nodes）等。

### 2.2 容量与流量的概念

容量（Capacity）指的是流网络中每条边所能传输的最大流量，通常用一个非负实数表示。流量（Flow）则表示实际通过每条边传输的流量值，同样是一个非负实数。在网络流算法中，流量不会超过容量，即流量小于等于容量。

### 2.3 割与流网络的关系

割（Cut）是对流网络中的节点集合的一种划分，将节点分为两个不相交的部分。割由割集与割容量组成，割集表示割中包含的边，割容量表示从源点到汇点的最大流量。在流网络中，割与最大流之间存在着密切的关系，最大流等于最小割的容量。

通过精确定义节点、边、容量、流量、割等概念，能够清晰地描述任意网络流问题的建模过程，有助于后续的算法实现与分析。

# 3. Ford-Fulkerson算法原理

#### 3.1 Ford-Fulkerson算法的基本思想

在网络流算法中，Ford-Fulkerson算法是一种经典的求解最大流的方法。其基本思想是通过不断寻找增广路径来增加流量，直到无法找到增广路径为止。具体步骤如下：

1. 初始化流量为0。
2. 在残余网络中寻找增广路径，即从源点到汇点的路径，并找出路径上的最小容量。
3. 将最小容量加到流量中，并更新残余网络中对应路径的边的容量。
4. 重复步骤2和步骤3，直到无法找到增广路径为止，此时流量达到最大流量。

#### 3.2 增广路径的寻找

增广路径的寻找可以使用深度优先搜索（DFS