Graph Traversal Algorithms

In this lesson, you will learn the basic logic behind graph traversal. You 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:

  1. Breadth First Search (BFS)
  2. Depth First Search (DFS)

To understand these algorithms, you 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 lists or stacks. So how do you give 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 mean the vertices adjacent to these nodes.

With this in mind, begin the 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 in 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.

Look at the BFS algorithm in action:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.