Depth-first Search (DFS)
Explore how depth-first search (DFS) is used to traverse graphs by visiting the deepest nodes first. Understand node and edge classifications during DFS, and learn how to apply DFS to check graph connectivity and detect cycles. This lesson helps you master fundamental traversal techniques essential for graph algorithms in C++.
We'll cover the following...
After settling the basic terminology and learning about graph representations, let’s dive into our first actual graph algorithm. In this section, we’ll look into different ways of traversing graphs.
Unlike totally or partially ordered data structures, such as lists or trees, there is no canonical order in which the nodes of a graph should be explored. However, there are two standard algorithms to traverse graphs that define an order in which the nodes are visited: depth-first search (DFS) and breadth-first search (BFS). Although the algorithms are elementary, they can already be applied to solve a wide variety of graph problems with just basic modifications.
In this lesson, we will start by looking into depth-first search. ...