Neet 150
Graphs
DFS- Where is it used?
- DFS can be utilized for topological sorting in directed acyclic graphs (DAGs).
- It helps in finding paths between two vertices in a graph.
- DFS is effective for cycle detection in both directed and undirected graphs.
- It is also applied to solve one-solution puzzles.
- Additionally, DFS can determine whether a graph is bipartite or not.
Depth-first search
The depth-first search goes deep in each branch before moving to explore another branch.
Preorder Traversal
In preorder traversal, we traverse the root first, then the left and right subtrees.
public void traversePreOrder(Node node) {
if (node != null) {
visit(node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}
public void traversePreOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node current = root;
stack.push(root);
while(!stack.isEmpty()) {
current = stack.pop();
visit(current.value);
if(current.right != null) {
stack.push(current.right);
}
if(current.left != null) {
stack.push(current.left);
}
}
}
Inorder Traversal
We traverse the left subtree first, then the root, then finally the right subtree.
Inorder traversal for a binary search tree means traversing the nodes in increasing order of their values.
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
visit(node.value);
traverseInOrder(node.right);
}
}
public void traverseInOrderWithoutRecursion() {
Stack stack = new Stack<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
Node top = stack.pop();
visit(top.value);
current = top.right;
}
}
Postorder Traversal
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
visit(node.value);
}
}
public void traversePostOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node prev = root;
Node current = root;
stack.push(root);
while (!stack.isEmpty()) {
current = stack.peek();
boolean hasChild = (current.left != null || current.right != null);
boolean isPrevLastChild = (prev == current.right ||
(prev == current.left && current.right == null));
if (!hasChild || isPrevLastChild) {
current = stack.pop();
visit(current.value);
prev = current;
} else {
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
}
Graph DFS with Recursion
- We’ll start from a given node
- Mark current node as visited
- Visit current node
- Traverse unvisited adjacent vertices
public boolean[] dfs(int start) {
boolean[] isVisited = new boolean[adjVertices.size()];
return dfsRecursive(start, isVisited);
}
private boolean[] dfsRecursive(int current, boolean[] isVisited) {
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
dfsRecursive(dest, isVisited);
}
return isVisited;
}
Sources: https://www.baeldung.com/java-depth-first-search
DFS for Graphs sources
