Explore the basics of graph theory, learn to represent graphs in C++, and master essential algorithms like DFS and Dijkstra to solve complex optimization problems, including matching and network flow.

Graph algorithms are the core of many real-world applications of computer science,  such as automotive navigation or routing in computer networks. They’re also a common subject in coding interviews at top-tier tech companies.
 
In this course, we’ll learn about the basic concepts of graph theory and how to represent graphs as data structures in code. We’ll study essential graph algorithms such as depth-first search or Dijkstra's algorithm to traverse graphs and find shortest paths. Finally, we’ll learn to solve more complex optimization problems on graphs, such as matching and network flow problems.

Learn Graph Algorithms in C++

In this lesson, we want to prove that the Ford-Fulkerson method is actually guaranteed to find a maximum flow. To do this, we'll take a short detour into the territory of another graph problem, finding minimum cuts.

# The minimum cut problem

The minimum cut problem is another problem that can be posed in a flow network $G = (V, E, c)$. Given a source $s$ and a sink $t$, an $\mathbf{s}$**-**$\mathbf{t}$**-cut** is a partition of the vertices $V$ into two subsets $S$ and $T$, such that $s \in S$ and $t \in T$. 


The value $v(S, T)$ of an $s$-$t$-cut is the capacity of all edges that cross the cut from $S$ to $T$.
$$ v(S, T) = \sum_{u \in S, v \in T, (u, v) \in E} c(u, v).$$

As an example, let's take another look at the flow network from the previous lesson:  

digraph g {
    bgcolor="transparent"
    {rank=same a, t, st}
    {rank=same ss, s, b}
    splines=false
    ss,st[style=invis]
    s,a[color=blue]
    b,t[color=red]
    ss -> s
    t -> st
     
      
    s -> a [label="  2"]
    s -> b [label="2", color=green]
    a -> b [label="5", color=green]
    a -> t [label="1", color=green]
    b -> t [label="  2"]
    
}

Here, we’ve marked up an example cut with $S = \{s, a\}$ (blue) and $T = \{b, t\}$ (red). The edges crossing through the border of the cut are marked in green. The value of the cut is 
$$v(S, T) = 1 + 2 + 5 = 8.$$

However, it is  not a minimum cut because there is a cut with a smaller value:

digraph g {
    bgcolor="transparent"
    {rank=same a, t, st}
    {rank=same ss, s, b}
    splines=false
    ss,st[style=invis]
    s,a,b[color=blue]
    t[color=red]
    ss -> s
    t -> st
     
      
    s -> a [label="  2"]
    s -> b [label="2"]
    a -> b [label="5"]
    a -> t [label="1", color=green]
    b -> t [label="  2", color=green]
    
}

This cut $S = \{s, a, b\}, T = \{t\}$ is a cut with the minimum value of $3$.

# Cuts and flows

There is an interesting relationship between cuts and flows in flow networks. For any cut $(S, T)$ and any flow $f$, it holds that
$$v(S, T) \geq v(f).$$ 

In other words, flows can't be larger than cuts, and cuts can't be smaller than flows.

Let's see why this is the case. We have a flow $f$ which transports $v(f)$ units from the source $s$ to the sink $t$. Since $s \in S, t \in T$, at some point each unit of flow must leave $S$ and enter $T$, In other words, it must flow through an edge crossing the border between $S$ and $T$. Hence, $v(S, T)$, which is the capacity of these border-crossing edges, must be at least $v(f$).

This inequality between cuts and flows also allows us to link maximum flows and minimum cuts. Assume that we find a cut $(S^*, T^*)$ and a flow $f^*$ of equal value:
$$v(S^*, T^*) = v(f^*).$$
In that case, $f^*$ is a maximum flow, and $(S^*, T^*)$ is a minimum cut. There is no larger flow because flows can’t be larger than cuts, and there is no smaller cut because cuts can’t be smaller than flows.

# Correctness of the Ford-Fulkerson method

We can apply what we've learned about cuts and flows to prove the correctness of the Ford-Fulkerson method. 

Recall that Ford-Fulkerson attempts to augment a flow $f$ by finding an $s$-$t$-path in the residual network $G_f$. The algorithm terminates when such a path no longer exists.

Let $f^*$ be the flow returned by the Ford-Fulkerson method. We can use $f^*$ to define an $s$-$t$-cut $(S^*, T^*)$. Choose $S^*$ to be the vertices that are reachable from $s$ in the residual network. Because there is no $s$-$t$-path in $G_f$, we have $t \notin S^*$ and can set $T^* = V \setminus S^*$ to define a cut. 

To illustrate this, consider the flow computed by Ford-Fulkerson in our example network:

Explore the connection between maximum flows and minimum cuts.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Max Flow = Min Cut

The minimum cut problem