Graph Theory Problem Solving - Session 2 ( Graph Traversal - DFS and BFS )

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 the shortest distance from one source to all other nodes.
    • To find the 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.

Practice Problem
That's all for this article, in the next article we will be discussing Application of DFS - Connected Component, Articulation Point and Bridges. Before moving to the next session do practice the above problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you ).

If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by CODELABS3277

Comments

Post a Comment