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).
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); } } } }
O(V + E) where V is the number of vertices and E is the number of edges.
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); } } }
O(V + E)
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.
Take quizzes related to this topic and see where you stand!
Start Quiz Now