Aim :

To implement graph traversals using:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Theory

A graph is a data structure consisting of vertices (nodes) and edges (connections).

BFS (Breadth-First Search): Traverses level by level using a queue.

DFS (Depth-First Search): Explores as deep as possible along a branch using recursion or a stack.

Graph Representation:

• Adjacency Matrix: A 2D array where matrix[i][j] = 1 if there’s an edge between i and j.
• Adjacency List: An array of lists where each index represents a node and contains its neighbors.

Algorithm:

1️⃣ BFS Algorithm

1. Start from a given vertex.
2. Visit all adjacent unvisited nodes.
3. Use a queue to track nodes to explore next.
4. Repeat until all nodes are visited.

2️⃣ DFS Algorithm

1. Start from a given vertex.
2. Visit an adjacent unvisited node.
3. Use recursion (or a stack) to continue exploring.
4. Backtrack when no adjacent nodes remain.

BFS vs. DFS:

Feature	BFS	DFS
Uses	Queue (FIFO)	Stack (LIFO) or Recursion
Best For	Finding the shortest path	Pathfinding & connectivity
Time Complexity	O(V + E)	O(V + E)