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.

**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

**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,

whichone is to be usedwherewould 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 algorithmsdiffer in the way they explore nodesand 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 ***

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

LikeLike

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 🙂

LikeLike

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 ?

LikeLike

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.

LikeLike

EXCEPTIONAL Post.thanks for share..more wait.

LikeLike

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.

LikeLike