Experiment 12: BFS and DFS

Aim: Programs to implement BFS and DFS  

A graph is a non‑linear data structure consisting of a set of vertices (nodes) and edges (connections between nodes). It is used to represent relationships between objects. Graphs can be directed (edges have direction) or undirected (edges are bidirectional). They may also be weighted, where each edge carries a cost or value. Diagrammatically, a graph is shown as circles (vertices) connected by lines or arrows (edges). Graphs are widely used in computer science for modeling networks, social connections, maps, and many real‑world problems.

Breadth First Search (BFS)  

BFS is a graph traversal algorithm that explores vertices level by level. Starting from a source node, it visits all immediate neighbors before moving to the next level of nodes. BFS uses a queue data structure to keep track of nodes to be visited.  

- Algorithm (Steps):  

  1. Start from the source vertex and mark it as visited.  

  2. Insert it into a queue.  

  3. Remove a vertex from the queue, visit all its unvisited neighbors, and insert them into the queue.  

  4. Repeat until the queue becomes empty.  

- Example:  

  Consider a graph with vertices A, B, C, D, and E. Starting BFS from A, the traversal order would be: A → B → C → D → E.  

  Diagrammatically, BFS spreads outward like ripples, covering nodes layer by layer.

Depth First Search (DFS)  

DFS is another graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of nodes.  

- Algorithm (Steps):  

  1. Start from the source vertex and mark it as visited.  

  2. Push it onto a stack (or call recursively).  

  3. Visit an unvisited neighbor, mark it, and continue deeper.  

  4. If no unvisited neighbors remain, backtrack to the previous vertex.  

  5. Repeat until all vertices are visited.  

- Example:  

 For the same graph with vertices A, B, C, D, and E, starting DFS from A, the traversal order could be: A → B → D → E → C (depending on adjacency order).  

 Diagrammatically, DFS looks like a path that dives deep into one branch before returning to explore others.

Conclusion  

Through this experiment, we studied the concept of graphs and understood how BFS and DFS algorithms work. BFS explores nodes level by level using a queue, while DFS explores depth using a stack or recursion. Both methods are fundamental in computer science for solving problems related to connectivity, pathfinding, and network traversal.