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++

The next lessons discuss algorithms that solve flow problems in weighted graphs. Apart from direct applications in flow networks, they can also be applied to solve various kinds of matching or assignment problems.

# Example of a flow network

As an example, let’s consider the problem of transferring a large file on the internet from London to Frankfurt. We want to achieve the maximum possible throughput in doing so. On the way, we may need to pass several intermediate nodes, and each connection we use on the way has a limited data rate.


This situation can be modeled as a weighted graph where the edge weights correspond to the maximum throughput on each connection, for example,. in Megabit per second:


digraph g {
    bgcolor="transparent"
    rankdir=LR
    splines=false
    a[label=London]
    b[label=Amsterdam]
    c[label=Brussels]
    d[label=Paris]
    e[label=Hamburg]
    f[label=Strassbourg]
    g[label=Frankfurt]
    s, t[style=invis]
    
    s -> a
    a -> b[label=5]
    a -> d[label=8]
    b -> c[label=4]
    d -> c[label=3]
    b -> e[label=3]
    d -> f[label=4]
    c -> g[label=4]
    f -> g[label=5]
    e -> g[label=2]
    g -> t
}

Naturally, we’d like to utilize each connection at its full capacity. However, this is not always possible. For example, the outgoing connections from Amsterdam have a total capacity of 7 Mb/s, but the only incoming connection has a capacity of only 5 Mb/s, so the outgoing connections cannot be fully utilized.

The maximum network flow which can be achieved in this network is 10 Mb/s. There are actually several ways to obtain this maximum flow. The following image shows one of them:

digraph g {
    bgcolor="transparent"
    rankdir=LR
    splines=false
    a[label=London]
    b[label=Amsterdam]
    c[label=Brussels]
    d[label=Paris]
    e[label=Hamburg]
    f[label=Strassbourg]
    g[label=Frankfurt]
    s, t[style=invis]
      
    s -> a
    a -> b[label="5/5"]
    a -> d[label="5/8"]
    b -> c[label="3/4"]
    d -> c[label="1/3"]
    b -> e[label="2/3"]
    d -> f[label="4/4"]
    c -> g[label="4/4"]
    f -> g[label="4/5"]
    e -> g[label="2/2"]
    g -> t
}

# The maximum flow problem

Let's come up with a formalization of the flow maximization problem. The setting is a directed graph $G = (V, E, c)$, called a **flow network**, where $c : E \to \mathbb{N}$ is a weight function. The edge weights are the **capacities** of the edges, written as $c(u, v)$. 

The capacity of an edge is the maximum flow that can be pushed through that single edge. We assume that the capacities are integers, and only an integer amount of flow can be pushed through an edge.

There are also two special nodes in $V$: the **source** $s$ and the **sink** $t$. The source has no incoming edges, and the sink has no outgoing edges. In the example from above, the source is London, and the sink is Frankfurt. Our goal is to maximize the total network flow from $s$ to $t$. 

A flow in the graph is a specification of how many units of flow should be pushed through each edge. It is specified as a **flow function** $f : E -> \mathbb{N}$. However, for the flow to be valid, it needs to follow a few intuitive rules:

1. **Respect the capacity**: The flow through an edge $(u, v)$ can be the edge capacity at most. 
$$f(u, v) \leq c(u, v)  \qquad \forall (u, v) \in E$$
2. **In-flow = out-flow**: Except for the source and the sink, the flow entering a node $v$ must equal the flow exiting $v$.
$$\sum_{(u, v) \in E}f(u, v) = \sum_{(v, w) \in E}f(v, w) \qquad \forall v \in V \setminus \{s, t\}$$

There are no constraints on the outgoing flow of the source, so we can assume that we have an infinite amount of flow available to distribute from the source. 

The **value** $v(f)$ of a flow $f$ is the amount of flow that reaches the sink $t$:
$$ v(f) = \sum_{(u, t) \in E}f(u, t)$$

The value of a flow is also equal to the amount of flow that leaves the source $s$.
 
We are interested in finding a **maximum flow**, or, a flow of the highest possible value. In our example graph from above, the maximum flow has a value of $10$.

# Cyclic flows

The definition of a flow does not prohibit pushing flow around in cycles on the way from $s$ to $t$. For example, here is a flow of value $5$, which also pushes some additional flow through the cycle `a -> b -> c`: 

Learn about flow problems in graph networks.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

The Max Flow Problem

Example of a flow network