Traversing a Graph using Depth First Traversal

Earlier we have seen how to build a simple Graph using Adjacency List and how to traverse it using breadth first traversal. The Graph which was used is presented below.

Friend_Graph

Building on that we are going to see how to traverse that Graph using another popular approach known as “depth first traversal”, or DFT. This video acts as a supplement to this article.

At the end of this Post I have presented code written in C to show you how can DFS be implemented. After all we should be able to write the code and not just talk about the approach.

A popular application of depth first traversal is to do Topological Sorting or Ordering.

Understanding DFT

In DFT we pick a vertex to start with. In our example friendship graph we start with Ankur. We visit this and mark it as visited.

Next we explore the adjacent vertices to this vertex, like Reena. But we don’t explore the next adjacent vertex to Ankur i.e. Dikshit, instead we explore further and visit Nidhi, who is connected to Reena. So what we are doing is traversing the depths till we reach a leaf or a node that has been visited. Then we backtrack and start exploring the next adjacent node i.e. Dikshit.

Doesn’t this sound recursive? It is and as you will see our code makes use of recursion to perform DFT.

Continue reading “Traversing a Graph using Depth First Traversal”

Traversing a Graph using Breadth First Traversal

Earlier I have shown you how to build a simple Graph using Adjacency List. We used a Friendship Graph to demonstrate that. If you haven’t read that I will recommend you to take a look at the following two posts that cover Graphs and Queues, since we will make use of both these structures.

Friend_Graph

Building on that we are going to see how to traverse that Graph using a very popular approach known as “breadth first traversal”, or BFS.

At the end of this Post I have presented code written in C to show you how can BFS be implemented. After all we should be able to write the code and not just talk about the approach.

Few applications of Breadth First Traversal (BFT)

  • BFT can be used to generate a Tree. This tree can help us find out shortest distances from root node to other nodes. Also it can be used to find Paths between vertices.
  • BFT can be used to determine the connected components in a Graph. A connected component means that any vertex in that component can be reached from any other vertex in the same component.
  • It can help us solve Vertex Coloring problem, which has applications like assigning resources etc.

Understanding BFT

Let’s start by understanding BFT. In BFT we pick a vertex to start with. In our example friendship graph we start with Ankur. We insert this in a Queue (Q) and mark it as visited.

Continue reading “Traversing a Graph using Breadth First Traversal”

Basic Graph Data Structure to demonstrate Friendships

Graphs have numerous applications out of which Social Networks is quite popular.

In this Article I have tried to present a simple use case to demonstrate how to represent it using Adjacency Lists.  Idea is to help you get started with Graphs.

Since we are discussing friendships the Graph used is an undirected one.

Consider a simple case, we have a really small town with only 6 people. The figure below shows how they are connected to each other. So for example Ankur is friend with Dikshit and Reena.

Friend_Graph.png

So how can we capture this data?

A Graph is a set of Vertices and Edges. In our case the people are the vertices and the relationship between them are the Edges.

There are two popular ways to represent a Graph. One is the Adjacency Matrix approach and another one is the Adjacency List approach. The second one is more popular because of it’s efficiency. If you need more details on these two representations kindly visit the following links Adjacency Matrix  &  Adjacency List

Please drop a comment if you want me to explain these approaches as well. For now I want to keep things short and simple.

In the List approach we maintain an Array of Vertices and each Vertex in the Array has a Linked List which points to it’s Edges. See the figure below. I have shown one of the Linked List that shows Ankur’s connections.

AL

Now let’s see how to implement this using C. If you are not quite familiar with Arrays and Linked List I will recommend you to visit Wiki for the same. I have written sample programs for Array and Linked List here and I am planning to explain them soon.

Continue reading “Basic Graph Data Structure to demonstrate Friendships”