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

Let's see how we can adapt the graph representations introduced in the previous lessons to weighted graphs. Throughout this lesson, we'll use the following weighted graph as a running example:

digraph g {
    bgcolor="transparent"
    rankdir=LR
    0 -> 1 [label=5]
    1 -> 0 [label=3]
    1 -> 2 [label=7]
    1 -> 3 [label=4]
    2 -> 0:se [label=11]
    2 -> 3 [label=4]
}

# Weighted adjacency matrix

To represent a weighted graph using its adjacency matrix, we can simply use a matrix of integers instead of booleans. The entry $A[i,j]$ will be $0$ when there is no edge from $i$ to $j$, otherwise, it will be the weight of the edge $(i, j)$. Here is the weighted adjacency matrix of our example graph:

$$
\begin{pmatrix}
0 & 5 & 0 & 0 \\
3 & 0 & 7 & 4 \\
11 & 0 & 0 & 4 \\
0 & 0 & 0 & 0 
\end{pmatrix}
$$

For the implementation, we can simply reuse our naive implementation of the adjacency matrix as a nested `vector` of integers, this time corresponding to the weighted adjacency matrix.

Explore how weighted graphs can be implemented.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Representing Weighted Graphs

Weighted adjacency matrix