Problem Statement
In what traversal do we process all of a vertex's descendants before we move to an adjacent vertex?
Explanation
Depth First Search processes all descendants of a vertex before moving to adjacent vertices. DFS explores as deep as possible along each branch before backtracking.
Breadth First Search, also called level order or width first traversal, processes all vertices at the current level before moving to the next level. DFS uses a stack for implementation while BFS uses a queue. DFS is useful for detecting cycles, topological sorting, and maze solving.
Code Solution
SolutionRead Only
// DFS - Process all descendants first
void DFS(Node node, boolean[] visited) {
if (node == null) return;
visited[node.data] = true;
System.out.print(node.data + " ");
// Process all descendants before adjacent
for (Node neighbor : node.neighbors) {
if (!visited[neighbor.data]) {
DFS(neighbor, visited);
}
}
}
// BFS - Process level by level
void BFS(Node start) {
Queue<Node> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.data + " ");
queue.addAll(node.neighbors);
}
}