Skip to content

Instantly share code, notes, and snippets.

@sychonet
Last active June 10, 2022 08:47
Show Gist options
  • Save sychonet/0f52d6b550fb6fb5b233132419e8fff1 to your computer and use it in GitHub Desktop.
Save sychonet/0f52d6b550fb6fb5b233132419e8fff1 to your computer and use it in GitHub Desktop.
Pseudocode for basic BFS (Breadth First Search)
/**
* 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
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
// 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;
}
step = step + 1;
}
return -1; // there is no path from root to target
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment