Graph Traversal Algorithms

Introduction #

There are many applications for graphs, such as the GPS navigation system, shortest path finding, peer to peer networks, crawlers in the search engine, garbage collection (java), and even social networking websites.

Depending upon the problem under, the way we traverse a graph is important, since it can affect the time in which we reach the goal.

Types of Graph Traversals #

There are two basic techniques used for graph traversal:

1. Breadth First Search (BFS)
2. 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 lists or stacks. So how do we give the 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. Therefore, a level higher would consist of the vertices adjacent to these nodes.

With this is 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 you can reach every level of a starting vertex, one level at a time.

Now, let’s look at the BFS algorithm in action.

To build a graph based on BFS, start traversing from any vertex, call it currentVertex. If the adjacent vertices are yet already not visited, then print their values. Then, move on to children of the currentVertex.

Let’s look at BFS traversal in action!