Breadth First Search is an algorithm fo finding a specified node in a tree or graph. It works by first visiting the start node, and then visiting all of its children before any of the children's children.
- Generally utilizes a queue for keeping track of visited and unvisited nodes.
- Has a worst case time complexity of O(N+E) where N is the number of nodes and E the number of edges.
- Select a starting node and insert it into an empty queue.
- Given that the queue is not empty, extract the node from the queue and add all of its children to the queue for later processing.
- If extracted node is the node to search for, return the node.
- Repeat process with children now in queue until specified node is found or queue is empty.
Learn More
For more in-depth information, check out Geeks for Geeks.