Learn about the basic concepts of graph theory and how to represent graphs as data structures in code.

Become a C++ Programmer

Graph algorithms are the core of many real-world applications of computer science, such as automotive navigation or routing in computer networks. 

In this module, 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 the 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++

Before we start diving into graph algorithms, let’s introduce some of the basic concepts of graph theory that we’ll use throughout the course. 

## Directed graphs

We’ll start with the most basic question: what even is a graph? Let's look at an example. 

digraph g {
    graph[nodesep=0.4]
    splines=line
    rankdir=LR
    bgcolor="transparent"
    {rank=same; a, b}
    a -> b
    a -> c
    b -> c
    c -> b
}

The above graph consists of three nodes (named $a$, $b$, $c$) and four edges (drawn as arrows between nodes). The edges have a direction, indicated by the arrowhead. Hence, we call such a graph a **directed graph**:
- $a \to b$
- $a \to c$
- $b \to c$
- $c \to b$



The actual positioning of the nodes in the graph does not matter. In other words, it has no significance that in the above drawing $a$ is "above" $b$. In fact, here is the same graph drawn in a different layout:

digraph g {
    graph[nodesep=0.4]
    splines=line
    rankdir=BT
    bgcolor="transparent"
    {rank=same; a, b}
    a -> b
    a -> c
    b -> c
    c -> b
}

In other words, a graph is completely described by its set of nodes and edges.

By convention, the capital letter $V$ (for **v**ertices) is used to denote the set of nodes. In our example graph, we have 

$$V = \{a, b, c\}.$$

To denote the set of edges, we use the capital letter $E$. Each edge is a pair of two vertices, its **source** and **target**. In our example graph,

$$E = \{(a, b), (a, c), (b, c), (c, b)\}.$$

In total, a graph $G$ can then be written as:

$$ G = (V, E) \quad\text{ with }\quad E \subseteq V \times V.$$

For our example graph,

$$ G = (\{a, b, c\}, \{(a, b), (a, c), (b, c), (c, b)\}.$$

In this course, we’ll only consider graphs whose edges fulfill the following properties:
- There are never two edges with the same source and the same target.
- There are no "self-loop" edges of the form $(v, v)$.

Such graphs are called **simple graphs**. The following figure shows the two forbidden situations that were described above.


Before we start diving into graph algorithms, let’s introduce some of the basic concepts of graph theory that we’ll use throughout the course. 

# Directed graphs

We’ll start with the most basic question: what even is a graph? Let's look at an example. 

Learn about the difference between directed and undirected graphs.

Directed and Undirected Graphs

Directed graphs