Graph Search

About breadth first search and depth first search on graphs.

I was revisiting the graph traversal and search algorithms. Specifically “breadth first search” and “depth first search”. So, the blog will be about these. I will try to decode what they refer to. So hop on.


Why graphs ?

I have been interested in wireless networking and routing through my recent graduate studies. Graphs are critical to understanding  and analyzing how one can efficiently route packets on the internet. Hence, my interest in this topic !

Further, graphs can be used to solve range of problems from finding shortest path between nodes in a network (internet routing), finding efficient flights for you between cities (yes ! Expedia et al) , finding your friends and their friends on social media with common liking (Facebook yo!) and so on…

[Note : Moment you hear connections and/ paths – “Graphs” should pop on your mind]

What is a graph / data structures used to represent it?

Read here


BFS / DFS ?

BFS and DFS provide a way to explore a graph starting at any given node. As the name indicates, one search or traversal goes breadth first and the other goes depth first. Okay, don’t break your head over what breadth and depth.Shown below is how we would start exploring the neighbor nodes starting at any node in an “acyclic graph“. [A] and [B] show acyclic graph being explored with DFS and BFS.

In the snapshot, starting node is marked “A” in orange and nodes being explored in first run are marked blue, second run are marked green and third with yellow.

d_b_1

Fig [1] . BFS and DFS on a connected acyclic graph (tree)

Yes, this can be extended to cyclic graphs as below. How we begin exploring the graph is indicated by the arrows, starting at point A.

BFS : A, B,D, G, C,E,F

DFS : A,B, C,D,E,F,G

bfs_dfs_loop.png

Fig [2] . BFS and DFS on a connected cyclic undirected graph

Essentially in DFS, we pick a directly connected neighbor and explore its neighbor and so on till the end of the chain of unvisited nodes and then move on to next directly connected neighbor and so on. Think of it like you are exploring a path in a maze problem to it’s full length, to see if it can get you out.We can get the longest path/most expensive path using this technique. Also, used in topological sorting – sorting based on hierarchy (directories)

With BFS,  we explore directly connected neighbors first , then pick one neighbor at a time and explore its first neighbors (imagine a ripple in water). We continue exploring  how ripples go.  This technique helps us find “shortest path” between two nodes in a constant weight graph.

Data Structure used for DFS and BFS?

Read here.


Minimum Spanning Tree problem

Now, who has heard of a “Minimum spanning tree” ?

Spanning tree is a sub-graph that contains all vertices and is a “tree” (Yes !no cycles !).

Minimum spanning tree refers to a spanning tree  of connected , undirected graph that has least cost of all spanning trees. Are you wondering about directed graph MST ? It’s called “Arborescence problem”.  (let’s ignore it for now)

So, what do we mean by cost ? cost is the weight associated with each edge between two vertices. For example – cost can refer to distance in miles , when you are trying to find shortest path with multiple stop points on a map or it can be price of planes tickets between nodes (cities) or also the time delay incurred between nodes(routers) (internet routing) and so on.

So, if the weights of all edges is a constant or equal (ie., the cost associated with adding an edge to spanning tree is same  for all edges), any spanning tree is a minimum spanning tree.

Now, to find a minimum spanning tree in undirected  equal weighted graph, we just need to traverse all nodes of the graph once. Hence, in this case the graph traversal algorithms discussed above – BFS and DFS essentially would take same time (linear time – O(|V|+|E|) ,  where |V| is the  number of vertices and |E| is the number of edges in the graph) in finding a minimum spanning tree. Essentially, they achieve the same thing- exploring all nodes in a graph.

However, which one is to be used where would depend on “how” you go about exploring the nodes of the graph and “what” is it that you are looking to solve. BFS and DFS algorithms differ in the way they explore nodes and thus how they are implemented. More info available here

Make sure to read the blogs linked in here for a better understanding.

*** That’s all folks ***

  1. I wanted to thank you for this amazing read!! I undoubtedly appreciating every little touch of it I have you
    bookmarked to have a look at new material you post.

    Like

    Reply

  2. EXCEPTIONAL Post.thanks for share..more wait.

    Like

    Reply

  3. Could you elaborate on spanning tree ? What you mean by : sub graph containing all vertices, you mean all vertices of the parent graph which could be cyclic?
    And what is the use of a spanning tree ?
    Do spanning trees always exist ?

    Like

    Reply

    1. Hi Hitesh,
      Spanning tree essentially refers to connecting all nodes/vertices in a graph, touching each node/vertex exactly once and eliminating loops ( it’s a tree – no loops). So, in effect if you were to make a spanning tree for a “cyclic” graph, this would mean you would build a sub graph without cycles and visiting every vertex once.
      Example usage : If you set out to visit “n” different places (problem can be represented as a graph with each place being a vertex and the distance between two places being the weight of the edge)- you can plan a route where you visit all places using spanning tree – if you want the “lowest distance stretch” to visit all n places- you would use minimum spanning tree.
      Yes, spanning trees would always exist if your graph is connected and undirected.

      Like

      Reply

  4. That’s a good question. Answering that would require more explanation than picking one. You use BFS or DFS is really dictated by the problem you are solving. One can be faster than the other in completing a task. If both can solve a given problem (no element of which is faster), then it is a matter of choice based on how huge your graph is , the specifications of the system on which you are implementing etc. I will be covering more details soon in another blog on implementation of BFS and DFS. Keep reading 🙂

    Like

    Reply

  5. Which is commonly used DFS or BFS? Does one have advantage over the other – since same number of vertices and edges?

    Like

    Reply

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: