Graph Traversal Algorithms
In this lesson, we will learn the basic logic behind graph traversal, and we will see how it applies to the two most famous graph traversal algorithms.
We'll cover the following
Types of Graph Traversals #
There are two basic techniques used for graph traversal:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
In order to understand these algorithms, we will have to view graphs from a slightly different perspective.
Any traversal needs a starting point, but a graph does not have a linear structure like arrays or stacks. So how do we give a graph traversal a better sense of direction?
This is where the concept of levels is introduced. Take any vertex as the starting point; this is the lowest level in your search. The next level consists of all the vertices adjacent to your vertex. A level higher would be the vertices adjacent to these nodes.
With this in mind, let’s begin our discussion on the two graph traversal algorithms.
1. Breadth-First Search #
The BFS algorithm earns its name because it grows breadth-wise. All the nodes at a certain level are traversed before moving on to the next level.
The level-wise expansion ensures that for any starting vertex, you can reach all others, one level at a time.
Let’s look at the BFS algorithm in action:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.