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 use graph traversal to separate a directed graph into its strongly connected components. Such a decomposition can reveal useful information on the graph structure and can be the first step for more involved graph algorithms.

# Strongly connected components

Recall that a directed graph is called strongly connected when any pair of nodes can reach each other. Even if the whole graph is not strongly connected, it can be split up into parts called its **strongly connected components (SCCs)**. 

The following illustration shows a graph $G$ with three strongly connected components, marked in green, red, and blue, respectively.

digraph g {
    bgcolor="transparent"
    splines=false
    {rank=same; 2, 3}
    {rank=same; 0, 6}
    4, 1 [group=1]
    nodesep=0.4
      
    0, 1, 4, 6 [color=green]
    2, 3 [color=red]
    5 [color=blue]
    
    0 -> 1
    1 -> 4
    4 -> 0
    0 -> 6
    6 -> 4
    4 -> 5
    3 -> 2
    3 -> 5
    2 -> 3
    2 -> 5
}

For example, the nodes $0$ and $4$ are in the same SCC, as we can reach node $0$ from node $4$ and also reach node $4$ from node $0$ (via node $6$). On the other hand, nodes $4$ and $5$ are in distinct SCCs: although we can go from node $4$ to node $5$, there is no way to go from node $5$ to node $4$.

After identifying strongly connected components in a graph $G = (V, E)$, we can **contract** them to form a new graph $G'$, called the **contracted component graph** of $G$. The nodes of the contracted component graph are the SCCs of $G$. There is an edge between SCCs $X$ and $Y$ whenever there are $u \in X, v \in Y$ such that $(u, v) \in E$. The following figure shows the contracted component graph $G'$ of our example graph $G$ from above.

Learn how to split a graph into its strongly connected components.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Application 2: Strongly Connected Components

Strongly connected components