Graph Basics

graph_basics2

In this blog we will try to touch upon the basics of graph that one needs to know. Starting from what are edges or vertices, types of graphs there are – to – what are the data structures available to represent graphs in computer memory. So, let’s get started ! Continue reading “Graph Basics”

Graph Search

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