Algorithm
Graph and tree search algorithms |
---|
|
Listings |
|
Related topics |
|
The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as follows:
- Enqueue the root node
- Dequeue a node and examine it
- If the element sought is found in this node, quit the search and return a result.
- Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
- If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
- If the queue is not empty, repeat from Step 2.
Note: Using a stack instead of a queue would turn this algorithm into a depth-first search.
Read more about this topic: Breadth-first Search