Hello its me again Drifter Programming! Today we get into **Java Graphs** again talking about the **Maximum Flow Problem **and how we solve it using the **Ford-Fulkerson Algorithm**! This algorithm depends on and uses an** ****Graph Traversal algorithm** (DFS or BFS) and so I suggets you check out those first if you haven't already! I will implement the main algorithm using the Breadth-First-Search (BFS) algorithm. So, without further do let's get started!

## Max Flow Problem:

Suppose a **flow network** were **each edge has a maximum flow capacity**. The max flow problem is all about **finding the maximum flow **that we can get when going **from a single-source vertex to a destination** **vertex**. An **edge can't exceed it's capacity**.

This information can be useful in **computer networks** to find the maximum bandwidth that an connection can have or even at finding the maximum water capacity of an **water supply network**!

This problem can be represented as an Graph again were** each Edge has a maximum flow capacity** or weight and we then try to find the maximum flow using an algorithm. I will use the **Adjacency Matrix representation** that we also used in the Floyd Warshall algorithm, but I will **change the initialization of the Edges** (edge doesn't exist) **to zero** instead of MAX_VALUE or infinity. In the same way we will use the **BFS Algorithm**, but change it so that **it checks for an path from one specific source vertex to an destination** vertex and also **stores the path information in an parent array**.

The main algorithm is the **Ford-Fulkerson Algorithm** that does the following:

- It gets a graph and source and destination vertices as Input
- It creates an residual graph initialized equal to the input graph and initializes maxflow=0
- It loops as long as BFS (or DFS) returns a path from source to vertex and

- Finds the maximum path flow
- Updates the residual graph and reverse edges along the path
- Adds the path flow to the maxflow

4. Lastly returns the max flow

There is also another algorithm based on this one called **Edmonds-Karp**, but I will not cover it. You can check out some information here in wikipedia.

## Ford-Fulkerson Java Implementation:

As I already told you we will use the Graph from last time, but tweak it so that it initializes edges as 0 instead of Infinity. So, we only need a Graph class that will do all the Graph work for us. The main algorithms BFS and Ford-Fulkerson will be inside of the TestGraphs class as always.

So, the **classes **look as following:

**Graph Class:**

**BFS Algorithm:**

**Ford-Fulkerson Algorithm:**

**The rest of the TestGraphs class:**

The **Console **prints out:

And this means that the maximum flow from 0 to 4 is 15.2.

You can download the code in the following links at **pastebin**:

TestGraphs class that contains the algorithms also

You again can put them in a package with the name I put or remove the declaration.

And this is actually it for today!

I have two more algorithms that have to do with finding Hamiltonian and Eulerian Circuits in a Graph, but I haven't implemented them yet and so it might take some time! If you have any suggestions for other algorithms that I should cover don't be shy just tell me! :)

Bye!