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

# Defining the problem

The **minimum spanning tree (MST)** problem deals with connected, weighted, undirected graphs $G = (V, E, w)$. Here, the weights can be interpreted as costs, and the goal is to select some subset of edges $F \subseteq E$ that connect the nodes of $V$ in a cost-optimal way. In particular, we want
- $F$ contains enough edges such that they connect all nodes of $V$
- the total cost of the edges in $F$ is as small as possible.

As an example, consider the following weighted graph:

graph g {
    bgcolor="transparent"
    rankdir=LR
    splines=false
		a, c[group=1]
    b, d[group=2]
    {rank=same; a, e}
      
    a -- b[label=7]
    b -- c[label=8]
    c -- a[label=2]
    d -- a[label=8]
    d -- b[label=3]
    e -- a[label=4]
    e -- c[headlabel=6, labeldistance=7, labelangle=-7]
}

We can think of the nodes as representing cities, and the edges representing distances between them. Now, assume that we want to build a railroad network to connect these cities. Laying down train tracks is expensive, so we’ll want to find a way to connect all the nodes using the existing edges while keeping the total edge cost to a minimum.

In fact, this translates to finding a subset $F \subseteq E$ of minimal cost which connects $V$. The solution is given below, with the edges of $F$ highlighted in blue:

graph g {
    bgcolor="transparent"
    rankdir=LR
    splines=false
		a, c[group=1]
    b, d[group=2]
    {rank=same; a, e}
      
    a -- b[label=7, color=blue]
    b -- c[label=8]
    c -- a[label=2, color=blue]
    d -- a[label=8]
    d -- b[label=3, color=blue]
    e -- a[label=4, color=blue]
    e -- c[headlabel=6, labeldistance=7, labelangle=-7]
}

The total cost of $F$ is
$$ w(F) = \sum_{e \in F} w(e) = 4 + 2 + 3 + 7 = 16.$$
There is no other subset of $E$ that connects all nodes and has a lower cost.

# Introducing trees

In the language of graph theory, we can formulate the task like this:

> **(MST problem)** Given a connected, weighted, undirected graph $G = (V, E, w)$, find a **subgraph** $T = (V, F, w)$ such that $T$ is connected and $w(F)$ is minimal.

Saying that $T$ is a **subgraph** of $G$ simply means that $T$ contains only nodes and edges that are also in $G$. In this case, the set of nodes are identical, although the set of edges might only be a subset of $E$. 

As we have seen above, the weight $w(F)$ of the set of edges $F$ is obtained by summing the weight of the individual edges:
$$ w(F) = \sum_{e \in F} w(e).$$

Why do we call this task the Minimum Spanning Tree problem? Let’s think a bit about what the graph $T$ will look. By definition, we already know $T$ is connected. We can also claim that $T$ must be *acyclic*. 

This can be inferred from the fact that $T$ has a minimum cost. If there was any cycle in $T$, we could remove one of its edges and obtain a graph that is still connected but has a lower cost. The following picture illustrates this.

Get introduced to the minimum spanning tree problem.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

The Minimum Spanning Tree Problem

Defining the problem