Introduction
Breath First Search (BFS)
public class BFSTest {
static void bfs(int start, List<List<Integer>> graph) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty) {
int node = queue.poll();
System.out.println(node);
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
queue.add(neighbor);
visited[neighbor] = true;
}
}
}
}
public static void main(String[] args) {
int n = 5;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
graph.get(0).addAll(Arrays.asList(1, 2));
graph.get(1).addAll(Arrays.asList(0, 3, 4));
graph.get(2).addAll(Arrays.asList(0));
graph.get(3).addAll(Arrays.asList(1));
graph.get(4).addAll(Arrays.asList(1));
bfs(0, graph);
}
}
The queue data structure is largely associated with BFS.
Time Complexity: O(V + E)
O(V) part → you visit each vertex once.
O(E) part → for every vertex, you also look at its edges (neighbors) once.
Even if you skip already visited vertices, the algorithm still checks every edge at least once (to see if the neighbor has been visited).
👉 So total work = visiting all vertices (V) and examining all edges (E). Hence, O(V + E) time complexity.
Space Complexity: O(V)
Depth First Search (DFS)
public class DFSTest {
static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
visited[node] = true;
System.out.println(node);
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
public static void main(String[] args) {
int n = 5;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
graph.get(0).addAll(Arrays.asList(1, 2));
graph.get(1).addAll(Arrays.asList(0, 3, 4));
graph.get(2).addAll(Arrays.asList(0));
graph.get(3).addAll(Arrays.asList(1));
graph.get(4).addAll(Arrays.asList(1));
boolean[] visited = new boolean[n];
dfs(0, visited, graph);
}
}
The stack data structure is largely associated with DFS.
For example,
A
/ \
B C
/ \
D E
dfs(A)
├─ dfs(B)
│ ├─ dfs(D)
│ │ └─ return ← nowhere to traverse (stack pop)
│ ├─ dfs(E)
│ │ └─ return ← nowhere to traverse (stack pop)
│ └─ return ← all children of B was searched (stack pop)
├─ dfs(C)
│ └─ return ← c has no children (stack pop)
└─ return ← all children of A was completely searched
In other words, the most recently called dfs() function returns first (LIFO — Last In, First Out), which is exactly how a stack works!
Time Complexity: O(V + E)
Space Complexity: O(V)
| Graph Type | DFS/BFS Actual Ops | Big-O |
| ---------- | ------------------ | -------- |
| Undirected | V + 2E | O(V + E) |
| Directed | V + E | O(V + E) |
BFS vs DFS: Practical Applications in Permutation Generation
- When constructing all permutations of n elements, what is the advantage of Backtrack-DFS over simple BFS?
When constructing all permutations of a set of elements, such as [1, 2, 3], both BFS and DFS can be used to explore possible arrangements. BFS generates permutations level by level, storing all partially constructed sequences in a queue. For example, it would first enqueue [1], [2], [3], then expand these into [1,2], [1,3], [2,1], [2,3], [3,1], [3,2], and finally [1,2,3], [1,3,2], etc. While BFS ensures a systematic exploration, it requires significant memory to maintain all partial sequences. DFS with backtracking, on the other hand, explores each sequence depth-first, building one complete permutation at a time and then backtracking to explore alternatives. Using the same example, DFS would go from [] → [1] → [1,2] → [1,2,3], then backtrack to [1,3] → [1,3,2], and so on. This approach uses much less space, as only the current path and visited elements need to be stored, making DFS with backtracking especially efficient for combinatorial problems.
BFS
Level 0: []
Level 1: [1] [2] [3]
Level 2: [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
Level 3: [1,2,3] ...
> Store every case of permutations into queue -> requires a lot of Space
DFS (Backtracking)
[]
├─ 1 → [1]
│ ├─ 2 → [1,2]
│ │ ├─ 3 → [1,2,3] (output) → backtrack
│ └─ 3 → [1,3]
├─ 2 → [2] ...
> Use less spaces
Type of tree edges in graph Traversal
When performing BFS and DFS on a graph, every edge you encounter can be categorized into one of several types:
- tree edges, back edges, forward edges, and cross edges
A tree edge is an edge that leads to a vertex that has not yet been visited — it represents a true discovery in the DFS tree structure.
On the other hand, all back, forward, and cross edges are collectively called non-tree edges, because they don’t belong to the BFS or DFS tree itself.
A back edge connects a vertex to one of its ancestors in the DFS tree, indicating the presence of a cycle in directed graphs.
A forward edge connects a vertex to one of its descendants that has already been explored,
while a cross edge connects two vertices that belong to different DFS trees or subtrees.
Understanding these classifications is crucial for analyzing graph properties such as detecting cycles, finding strongly connected components, or performing topological sorting.
| Algorithm | Possible Edge Types | Description
| --------- | -------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| DFS | Tree, Back, Forward, Cross | DFS explores deeply along each branch, so ancestor–descendant relationships can vary widely. |
| BFS | Tree, Cross | BFS explores in increasing order of distance (level), so edges only connect vertices within the same or adjacent levels — back and forward edges never appear. |