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

The second important traversal algorithm for graphs is breadth-first search (BFS). The main concept of BFS is that the closest not yet explored node is explored first. This is exactly the opposite strategy compared to DFS.

# Explanation of BFS

Let’s execute the BFS algorithm on an example graph as we did for DFS.



In the end result of a BFS execution, all nodes are marked as finished and all distances to the starting node are recorded.

We’ll only discover nodes reachable from the starting vertex, just like we saw for DFS. If we want to explore the whole graph, running further BFS executions from yet undiscovered vertices is needed.

# Edge types in BFS

When discussing DFS, we’ll split up the edges into different types: discovery edges, back edges, and redundant edges. The back edges were very useful in discovering cycles. So why are we not doing the same in BFS?

It is not easy to identify back edges in BFS, due to the different node traversal order. When we find an edge that leads “back” to an already discovered or finished node, we cannot be sure that this guarantees a cycle. 

For example, check out the following graph where BFS was started from node `a`, and the current node is `d`. We find edges leading from `d` to the finished node c and the discovered node `e`, but neither of them are part of a cycle. In fact, the graph is acyclic.

digraph g {
    bgcolor="transparent"
    splines=false
    rankdir=LR
    a, c [group=1]
    {rank=same; d,e}
    nodesep=0.4
    
    a[label="a (0)",style="filled",fillcolor="blue1",fontcolor="white"]
    b[label="b (1)",style="filled",fillcolor="blue1",fontcolor="white"]
    c[label="c (1)",style="filled",fillcolor="blue1",fontcolor="white"]
    d[label="d (2)"style="filled"]
    e[label="e (2)"style="filled"]
    a -> b
    a -> c
    b -> d
    b -> e
    d -> c
    d -> e
}

Since the detailed edge classifications for BFS are not as useful, they are usually omitted. However, keeping track of which edges are discovery edges can be important.

# Application: Shortest paths

We already saw that executing BFS yields us the distance of each node to the starting vertex. We can also use BFS to compute the shortest path between two vertices $u$ and $v$.

To do so, we simply run BFS from the starting vertex $u$. Each time we discover a new node $b$ from the current node $a$, we mark $a$ as the parent of $b$ (just like we did in our implementation of DFS for undirected graphs).

Once we reach node $v$, we can go back to its parent, grandparent, and so on, until we reach node $u$ again. The sequence of ancestors, from oldest to youngest, corresponds to the shortest path from $u$ to $v$.

The following image shows the result of our BFS on the example graph, with all discovery edges marked in green (signifying the parent relationship between nodes).

Discover how to traverse graphs using breadth first search.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Breadth First Search (BFS)

Explanation of BFS

Edge types in BFS