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.

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.

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