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();
}
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();
}
Problem | Score | Companies | Time | Status |
---|---|---|---|---|
Path in Directed Graph | 150 |
|
42:29 | |
Water Flow | 200 |
|
75:01 | |
Stepping Numbers | 300 |
|
61:16 | |
Capture Regions on Board | 500 |
|
66:48 | |
Word Search Board | 500 |
|
60:30 |
Problem | Score | Companies | Time | Status |
---|---|---|---|---|
Path with good nodes! | 150 |
|
62:35 | |
Largest Distance between nodes of a Tree | 200 |
|
79:15 | |
Good Graph | 200 |
|
61:35 | |
Cycle in Directed Graph | 200 |
|
57:51 | |
Delete Edge! | 200 |
|
70:50 | |
Two teams? | 300 |
|
57:37 |
Problem | Score | Companies | Time | Status |
---|---|---|---|---|
Valid Path | 200 |
|
85:28 | |
Region in BinaryMatrix | 200 |
|
46:38 | |
Path in Matrix | 200 |
|
35:46 | |
Level Order | 300 |
|
29:55 | |
Smallest Multiple With 0 and 1 | 300 |
|
77:19 | |
Snake Ladder Problem! | 300 |
|
68:30 | |
Min Cost Path | 300 |
|
72:16 | |
Permutation Swaps! | 300 |
|
61:28 |
Problem | Score | Companies | Time | Status |
---|---|---|---|---|
Commutable Islands | 200 |
|
78:44 | |
Possibility of finishing all courses given pre-requisites | 200 |
|
65:25 | |
Cycle in Undirected Graph | 200 |
|
54:34 | |
Mother Vertex | 200 |
|
49:26 | |
File Search | 200 |
|
28:51 | |
Black Shapes | 300 |
|
49:04 |
Problem | Score | Companies | Time | Status |
---|---|---|---|---|
Convert Sorted List to Binary Search Tree | 300 |
|
45:01 |
Problem | Score | Companies | Time | Status |
---|---|---|---|---|
Sum Of Fibonacci Numbers | 300 |
|
53:42 | |
Knight On Chess Board | 300 |
|
68:21 | |
Useful Extra Edges | 400 |
|
63:50 | |
Word Ladder I | 600 |
|
70:18 | |
Word Ladder II | 800 |
|
71:04 |
Problem | Score | Companies | Time | Status |
---|---|---|---|---|
Clone Graph | 500 |
|
57:25 |