Graph Search (Depth Search)


Depth Search is an algorithm that traverses a graph to find an item, the logic behinds this search is this, Let’s assume that the first node be A, and I am looking at the neighbour of A node and there are 3 neighbours, B,C,E are the nodes alphabeticaly in order.

The first node to be visited in this list is B, after, I am going to visit the neighbour of B’s node, and it has only one neighbour, and that is D, now the turn is D’s neighbour and that is only one, final node is G.

Then, the tour is A, B, D, G and if the item being searched has been found on this stage, then we terminate the process, if we can not find it, then we should backtrack from G to the previous node, and that is D and now I am searching D’s neighbours except G, and as there is not, I am going back to B, and I will search B’s neighbours, and as there is not, I am going back to A, and I am going to the neighbour which has already been unvisited, and that is C, so, I am going from C, and the unvisited neighbour of this node is F and there are not other unvisited neighbours of F and we still have not found the item being searched, we go backwards again.

I am continuing this process until I have found the item or I have already visited all nodes in the graph.

This search technique is similar to a recursive reasoning.


One response to “Graph Search (Depth Search)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: