Queue
Queue
is aFirst-in-First-out
Data Structure- Always can implement Queue by BFS
Queue sometimes are used to process some short path problem.
Pseudocode
/**
* Return the length of the shortest path between root and target node.
* 1. As shown in the code, in each round, the nodes in the queue are the nodes which are waiting to be processed.
* 2. After each outer while loop, we are one step farther from the root node. The variable step indicates the distance from the root node and the current node we are visiting.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
For making sure never visit same code twice, we can add the visited to mark if the is visited or not:
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> visited; // store all the nodes that we've visited
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to visited;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to visited;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
Stack
Stack
is aLast-in-First-out
Data Structure- Always can implement Stack by DFS
Pseudocode
Recursively implement DFS:
/*
* Return true if there is a path from cur to target.
*/
boolean DFS(Node cur, Node target, Set<Node> visited) {
return true if cur is target;
for (next : each neighbor of cur) {
if (next is not in visited) {
add next to visted;
return true if DFS(next, target, visited) == true;
}
}
return false;
}
Use Stack:
- Sometimes if the depth of recursion is too high, we might have some stack overflow, in that case, better to use default Stack implementation
/*
* Return true if there is a path from cur to target.
*/
boolean DFS(int root, int target) {
Set<Node> visited;
Stack<Node> stack;
add root to stack;
while (s is not empty) {
Node cur = the top element in stack;
remove the cur from the stack;
return true if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in visited) {
add next to visited;
add next to stack;
}
}
}
return false;
}
Comments
Join the discussion for this article at here . Our comments is using Github Issues. All of posted comments will display at this page instantly.