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

This lesson introduces the concept of **big-$\mathcal{O}$-notation** for describing the worst-case runtime of an algorithm. If you are already familiar with big-$\mathcal{O}$-notation, feel free to skip this lesson.

# Counting operations 

Computer science problems can be solved with various different algorithms. Naturally, this leads to the task of comparing different algorithms for the same problem to find out which one is the best. More often than not, this boils down to the question “which algorithm is the fastest?” 

To measure and compare the runtime behavior of algorithms, we can count the number of operations that the algorithm must perform compared to the size of its input. For illustration, consider the following `C++`-function that checks whether there are two elements in a `vector` that sum to zero.

#include <iostream>
#include <vector>
using namespace std;

bool twoSum(vector<int> numbers) {
    for (int a : numbers) {
        for (int b : numbers) {
            int sum = a + b;
            if (sum == 0) { 
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<int> example {-2, 3, 2, 6};
    cout << (twoSum(example) ? "true" : "false");
}

Let's say that we pass a `vector` with $n$ elements to `twoSum`. How many operations will it perform? 

Actually, this will depend on the contents of the vector. If the first two elements are already summed to zero, the function will finish much quicker than if the last two elements sum to zero. Therefore, we usually focus on the worst-case runtime of an algorithm. In the case of `twoSum`, the worst case happens when there are no two numbers of the `vector` that sum to zero. In that case, both loops run over all elements and finally return `false`.

So, let's count the operations that `twoSum` performs in the worst case on an input `vector` of size $n$. There are two nested `for`-loops looping over $n$ elements, so the code inside these loops is executed $n^2$ times. There are two statements happening there: the addition and the `if`-condition. This makes $2n^2$ operations. 
Finally, there is the `return`-statement after the loops, accounting for one more operation. Our `twoSum` function performs $2n^2 + 1$ operations in the worst case. 

# Towards big-$\mathcal{O}$-notation

While operation counting is a valid and precise way to measure an algorithm's runtime, it's also quite tedious. Computer scientists usually use the so-called **big-$\mathcal{O}$-notation** instead. In this notation, our `twoSum` function's runtime would be written simply as $\mathcal{O}(n^2)$. 

There is a rigorous mathematical definition of the $\mathcal{O}$-symbol, but we will not cover that in this course. An intuitive understanding of its meaning will be sufficient.

# Only the largest growing term counts

The first rule of big-$\mathcal{O}$-notation is that we’ll only keep the fastest growing out of a sum of several terms. In our example of  $2n^2 + 1$ operations of `twoSum`, we’ll only keep the quadratic term $2n^2$  and ignore the constant $1$.

To give another example, if an algorithm takes $0.5n^3 + 50\log n + 15n$ operations, we’ll only keep the $0.5n^3$  term. This is because the cubic function grows much faster than the linear and the logarithmic component, so the cubic term will dominate the runtime as the input $n$ grows large.

Use big-O-notation for analyzing algorithms.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Excursion: Algorithm Analysis

Counting operations