DFS :
Algorithmic Steps
Step 1: Push the root node in the Stack.
Step 2: Loop until stack is empty.
Step 3: Peek the node of the stack.
Step 4: If the node has unvisited child nodes, get the unvisited child node, mark it as traversed and push it on stack.
Step 5: If the node does not have any unvisited child nodes, pop the node from the stack.
Based upon the above steps, the following Java code shows the implementation of the DFS algorithm:
public void dfs() {
//DFS uses Stack data structure
Stack s = new Stack();
s.push(this.rootNode);
rootNode.visited = true;
printNode(rootNode);
while(!s.isEmpty()) {
Node n = (Node)s.peek();
Node child = getUnvisitedChildNode(n); // Essentially this function goes through the neighbors of n, and finds the one with node.visited = false
if(child != null) {
child.visited = true;
printNode(child); // print the node as you like.
s.push(child);
}
else {
s.pop();
}
}
//Clear visited property of nodes
clearNodes();
}
BFS
Algorithmic Steps
Step 1: Push the root node in the Queue.
Step 2: Loop until the queue is empty.
Step 3: Remove the node from the Queue.
Step 4: If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in the queue.
Based upon the above steps, the following Java code shows the implementation of the BFS algorithm:
public void bfs() {
//BFS uses Queue data structure
Queue q = new LinkedList();
q.add(this.rootNode);
printNode(this.rootNode);
rootNode.visited = true;
while(!q.isEmpty()) {
Node n = (Node)q.remove();
Node child = null;
while((child = getUnvisitedChildNode(n)) != null) {
child.visited = true;
printNode(child);
q.add(child);
}
}
//Clear visited property of nodes
clearNodes();
}
Video Courses
