Graph Traversal

Things to be discussed in this article,
  • Why graph traversal?
  • Depth-first Search (DFS)
  • Breadth-first Search (BFS)
Graph Traversal
Graph traversal is a process of visiting all vertices in a Graph. Why do we ever need to traverse through a graph? The simple answer is to get information out of that Graph. Now your question would be that what we will do with that information? For this, I'll say that this information will help in our Real-life applications such as building a stable internet network, to find shortest route from source city to the destination city, finding the probable faulty zone in Network, etc.

So, in particular, we have two different methods of graph traversal which are widely used application based. The first one is Depth-First Search and the second one is Breadth-First Search. Below we describe both the algorithm

Depth-first Search
  • The depth-first search is a straightforward graph traversal technique. 
  • The algorithms begin at a starting node,  and proceeds to all other nodes that are reachable from the starting node, and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.
  • The depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other paths of the graph.
  • The algorithm keeps track of visited nodes so that it processes each node only once.
  • Running time of DFS Algorithm = O( V+E )
  • Application of DFS
    • To find the number of Connected Component.
    • To find shortest distance from one source to all other nodes.
    • To find presence of a cycle in a graph.
    • To find the topological sorting of the graph.
    • To find Articulation Points, Bridges in a Graph.
    • etc.
  • The below is an explanation video for Depth-first Search.

  • Implementation
    • A depth-first search can be implemented using recursion.
    • The flowing DFS function begins a depth-first search at a given node.
    • The graph is stored as adjacency lists.
    • In the below implementation we try to find the distance of all nodes from a given source node for an undirected connected graph.


Breadth-first Search
  • Breadth-first search visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using a breadth-first search.
  • The breadth-first search goes through nodes one level after another. The first search goes through the nodes one level after another. 
  • First, the search explores the nodes whose distance from the starting node is 1, then nodes whose distance is 2, and so on. 
  • This process continues until all nodes have been visited.
  • Running time of DFS Algorithm = O( V+E )
  • Application of BFS
    • To find the number of Connected Component.
    • To find shortest distance from one source to all other nodes.
    • To find presence of a cycle in a graph.
    • To check whether the graph is Bipartite/ 2-Colourable or not.
    • etc.
  • The below is an explanation video for Breadth-first Search.

  • Implementation
    • A breadth-first search can be implemented using recursion.
    • The flowing BFS function begins a depth-first search at a given node.
    • The graph is stored as adjacency lists.
    • In the below implementation we try to find the distance of all nodes from a given source node for an undirected connected graph.
That's all for this article, in the next article we will be discussing Application of DFS - Connected Component. Before proceeding to the next session do solve the problem set Question.

If you find any error or want to add something in this article then please feel free to comment.
Thank You

Comments