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

In this lesson, we’ll apply the DFS algorithm to solve a task ordering problem.

# The topological sorting problem

Our goal is to order a set of tasks in a way that respects the dependencies between them. For example, let’s assume that you’re planning your activities for the day. Unfortunately, there is a collection of household chores that you’ll need to complete first, such as washing the dishes, withdrawing cash, grocery shopping, and cooking. Some of these activities may depend on each other. For instance, you need to shop for groceries before you can cook dinner. And you need to withdraw cash before you can shop for groceries.

These tasks and dependencies can be modeled in a **task graph**. Each task is a node of the graph, and there is an edge $(u, v)$ whenever task $v$ directly depends on task $u$. The following figure shows an example task graph.

digraph g {
    splines=false
    nodesep=1
    bgcolor="transparent"
    rankdir="LR"
    a [label="shop groceries"]
    b [label="cook dinner"]
    c [label="wash dishes"]
    d [label="withdraw cash"]
    e [label="cook lunch"]
      
    a -> b
    c -> b
    d -> a
    a -> e
    c -> e
    e -> b
    
}

Whenever there is a path $u \rightarrow v$ in the task graph, the task $v$ (directly or indirectly) depends on the task $u$. This means that we have to perform task $u$ before we can perform task $v$!

We are looking for an order in which we can perform the tasks, such that all such dependencies are respected. Speaking in graph-theoretic terms, we are looking for an ordering of the nodes with this property:
> Whenever there is an edge $(u, v)$, then $u$ occurs before $v$ in the ordering.

Such an ordering is called a **topological sort**. 

For example, the order
```
withdraw cash -> shop groceries -> wash dishes -> cook lunch -> cook dinner
```
is a valid topological sort. There can be more than one topological sort, the following order is another one:
```
wash dishes -> withdraw cash -> shop groceries -> cook lunch -> cook dinner
```
Meanwhile, the order
```
cook lunch -> withdraw cash -> shop groceries -> wash dishes -> cook dinner
```
is not a topological sort. For example, there is an edge `(wash dishes, cook lunch)`, but `cook lunch` appears before `wash dishes` in the order.

It is clear that a topological sort cannot exist when the graph contains cycles. With circular dependencies, there is no way we can complete all the tasks.

Practice applying DFS to compute topological sorts.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Application 1: Topological Sort

The topological sorting problem