Ugenz Academy/Tutorial

Graphtraversal

10 min read1,825 words

Reading progress

Keep learning

Graph Traversal — BFS & DFS

Graph traversal means visiting all reachable vertices/nodes of a graph systematically.

The two most important graph traversal techniques are:

  1. BFS — Breadth-First Search
  2. DFS — Depth-First Search

1. Why Do We Need Graph Traversal?

Suppose we have:

0 / \ 1 2 / \ \ 3 4 5

If we want to visit every node, we need some systematic method.

For example:

BFS:

0 → 1 → 2 → 3 → 4 → 5

It visits level by level.

DFS:

0 → 1 → 3 → 4 → 2 → 5

It goes as deep as possible first.

2. Graph Representation

Before traversal, we need to represent the graph.

The most common representation is an adjacency list.

For:

0 / \ 1 2 / \ \ 3 4 5

Adjacency list:

0 → 1, 2 1 → 0, 3, 4 2 → 0, 5 3 → 1 4 → 1 5 → 2

In C++:

vector<vector<int>> graph = { {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2} };

3. The visited Array

A very important concept in graph traversal is:

visited[]

Why?

Because graphs can contain cycles.

Example:

0 ─── 1 │ │ └── 2 ┘

If we keep visiting neighbors without remembering visited nodes, we could go:

0 → 1 → 2 → 0 → 1 → 2 → ...

This can continue forever.

So we maintain:

vector<bool> visited(n, false);

Initially:

visited: 0 0 0 0 0 0

When we visit node 0:

1 0 0 0 0 0

4. BFS — Breadth-First Search

BFS = Breadth-First Search

BFS visits nodes level by level.

It uses a:

Queue

Remember:

Queue = FIFO First In → First Out

5. BFS Example

Consider:

0 / \ 1 2 / \ \ 3 4 5

Starting from 0.

Level 0

0

Level 1

1 2

Level 2

3 4 5

Therefore:

BFS = 0 1 2 3 4 5

6. BFS Step-by-Step

Start:

Queue = [0]

Visit 0.

Its neighbors:

1, 2

Add them:

Queue = [1, 2]

Remove 1:

Queue = [2]

Add 1's unvisited neighbors:

3, 4
Queue = [2, 3, 4]

Remove 2:

Queue = [3, 4]

Add 5:

Queue = [3, 4, 5]

Then visit:

3 4 5

Final:

0 → 1 → 2 → 3 → 4 → 5

7. BFS C++ Code

#include <iostream> #include <vector> #include <queue> using namespace std; void bfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; // Mark start as visited visited[start] = true; // Put start into queue q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; // Visit all neighbors for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } }

Example:

int main() { vector<vector<int>> graph = { {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2} }; bfs(0, graph); return 0; }

Output:

0 1 2 3 4 5

8. Why Mark visited Before push()?

This is important.

Correct:

if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); }

We mark it immediately when adding it to the queue.

Otherwise, the same node could be added multiple times from different neighbors.

9. BFS Shortest Path

One of the most important applications of BFS is:

Shortest path in an unweighted graph

Example:

0 ─ 1 ─ 3 │ 2 ─ 4

Starting from 0:

Distance from 0: 0 = 0 1 = 1 2 = 1 3 = 2 4 = 2

BFS naturally explores:

distance 0 ↓ distance 1 ↓ distance 2 ↓ distance 3

Therefore, the first time BFS reaches a node, it has found the shortest number of edges from the source.

10. BFS Distance Code

vector<int> distance(n, -1); queue<int> q; distance[start] = 0; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); for (int neighbor : graph[node]) { if (distance[neighbor] == -1) { distance[neighbor] = distance[node] + 1; q.push(neighbor); } } }

For example:

distance[0] = 0 distance[1] = 1 distance[2] = 1 distance[3] = 2

11. DFS — Depth-First Search

Now let's look at DFS.

DFS = Depth-First Search

DFS explores as deeply as possible before coming back.

DFS uses:

  • Recursion, or
  • Stack

Remember:

Stack = LIFO Last In → First Out

12. DFS Example

Again:

0 / \ 1 2 / \ \ 3 4 5

Starting at 0.

DFS can go:

0 ↓ 1 ↓ 3

3 has no unvisited neighbor, so backtrack:

0 ↓ 1 ↘ 4

Then backtrack to 0:

0 \ 2 \ 5

One valid DFS order:

0 1 3 4 2 5

13. Recursive DFS

The most common implementation uses recursion.

void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, graph, visited); } } }

Call it:

vector<bool> visited(graph.size(), false); dfs(0, graph, visited);

14. How Recursive DFS Works

Suppose:

0 → 1 → 3

Call:

dfs(0)

Then:

dfs(0) ↓ dfs(1) ↓ dfs(3)

When 3 finishes:

dfs(3) ↑ dfs(1) ↑ dfs(0)

This is called:

Backtracking

The function returns to the previous node after finishing the deeper node.

The function call stack automatically behaves like a stack.

15. DFS Using an Explicit Stack

We can also avoid recursion.

void dfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); stack<int> st; st.push(start); while (!st.empty()) { int node = st.top(); st.pop(); if (visited[node]) continue; visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { st.push(neighbor); } } } }

Here:

DFS → Stack BFS → Queue

16. BFS vs DFS

FeatureBFSDFS
Full formBreadth First SearchDepth First Search
UsesQueueStack / Recursion
StrategyLevel by levelGo deep first
Shortest path in unweighted graph✅❌
Cycle detection✅✅
Connected components✅✅
Topological sortPossibleVery common
Maze solvingPossibleVery common
MemoryCan be large for wide graphsCan be large for deep graphs

17. Connected Components

Consider:

0 ─ 1 ─ 2 3 ─ 4 5

There are three separate components:

Component 1: 0 1 2 Component 2: 3 4 Component 3: 5

We can count them using DFS/BFS.

int components = 0; vector<bool> visited(n, false); for (int i = 0; i < n; i++) { if (!visited[i]) { components++; dfs(i, graph, visited); } }

Result:

components = 3

This is a very common DSA problem.

18. DFS for Cycle Detection

Consider:

0 ─ 1 │ │ └─2─┘

There is a cycle:

0 → 1 → 2 → 0

During DFS, if we encounter an already visited node that isn't simply the parent we came from, we can detect a cycle in an undirected graph.

Concept:

if (!visited[neighbor]) { dfs(neighbor, node); } else if (neighbor != parent) { // cycle found }

19. BFS and DFS on Trees

An important connection:

A tree is also a graph.

For a binary tree:

1 / \ 2 3 / \ 4 5

DFS gives traversals such as:

Preorder: 1 2 4 5 3

BFS gives:

Level Order: 1 2 3 4 5

So you can think:

Tree │ ├── DFS → Preorder / Inorder / Postorder │ └── BFS → Level Order

20. BFS and DFS Complexity

For an adjacency list:

V = number of vertices E = number of edges

Both BFS and DFS take:

Time = O(V + E)

Why?

Each vertex is visited once:

O(V)

And each edge is examined:

O(E)

Therefore:

O(V + E)

Extra space:

O(V)

because of:

visited[] queue / stack

21. Important Graph Traversal Problems

After learning BFS and DFS, you should be able to solve:

Beginner

  • Traverse a graph
  • Count vertices
  • Count edges
  • Search for a node
  • Check whether a path exists
  • Count connected components

Intermediate

  • Shortest path in an unweighted graph
  • Detect cycle
  • Number of islands
  • Flood fill
  • Bipartite graph
  • Rotten oranges
  • Clone graph

Advanced

  • Topological sorting
  • Course schedule
  • Dijkstra
  • 0-1 BFS
  • Strongly connected components
  • Bridges
  • Articulation points

22. The Most Important Mental Model

Remember these two:

BFS ↓ Queue ↓ Level by Level ↓ Shortest path in unweighted graph

And:

DFS ↓ Stack / Recursion ↓ Go Deep ↓ Backtrack

23. Complete BFS + DFS Example

#include <iostream> #include <vector> #include <queue> using namespace std; // BFS void bfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } // DFS void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, graph, visited); } } } int main() { vector<vector<int>> graph = { {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2} }; cout << "BFS: "; bfs(0, graph); cout << "\n"; vector<bool> visited(graph.size(), false); cout << "DFS: "; dfs(0, graph, visited); return 0; }

Output:

BFS: 0 1 2 3 4 5 DFS: 0 1 3 4 2 5

Final Summary

GRAPH TRAVERSAL | ┌─────────┴─────────┐ ↓ ↓ BFS DFS | | Queue Stack / Recursion | | Level by level Go deep first | | Shortest unweighted Backtracking path useful useful

The key complexity to remember:

BFS = O(V + E) DFS = O(V + E)

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy