Graph Traversal – BFS and DFS
📘 Data Structure and Algorithm
👁 84 views
📅 Nov 05, 2025
⏱ Estimated reading time: 1 min
Graph Traversal – BFS and DFS
Graph traversal is the process of visiting all the vertices in a graph. The two most common traversal techniques are Breadth-First Search (BFS) and Depth-First Search (DFS).
1. Breadth-First Search (BFS)
BFS explores all neighbors of a vertex before moving to the next level. It uses a queue for implementation.
// Example: BFS (C++) void bfs(int start, vectoradj[], int V) { vector visited(V, false); queue q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : adj[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } }
Time Complexity:
O(V + E) where V is the number of vertices and E is the number of edges.
2. Depth-First Search (DFS)
DFS explores as deep as possible before backtracking. It uses a stack (or recursion) for implementation.
// Example: DFS (C++) void dfs(int node, vectoradj[], vector & visited) { visited[node] = true; cout << node << " "; for (int neighbor : adj[node]) { if (!visited[neighbor]) { dfs(neighbor, adj, visited); } } }
Time Complexity:
O(V + E)
Applications
- Finding connected components
- Cycle detection in graphs
- Topological sorting (using DFS)
- Shortest path in unweighted graphs (using BFS)
Conclusion
BFS and DFS are fundamental graph traversal algorithms. BFS is ideal for level-based exploration, while DFS is useful for deep exploration and backtracking-based problems.
🔒 Some advanced sections are available for Registered Members
Register Now
Register Now
Share this Post
← Back to Tutorials