breadth-first_search_and_depth-first_search
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | Last revisionBoth sides next revision | ||
| breadth-first_search_and_depth-first_search [2016/07/30 17:31] – dwallace | breadth-first_search_and_depth-first_search [2017/02/09 12:21] – dwallace | ||
|---|---|---|---|
| Line 18: | Line 18: | ||
| Breadth-First Search (BFS) is a searching algorithm that utilizes the concepts involved with the queue data structure. BFS works by expanding all successors to a node before moving onto analyzing any of those successors. This is known as a first-in, first-out (FIFO) approach. As the search goes through the nodes, it analyzes which nodes are successors, and adds those nodes to the queue as they are found. Then, the search goes back to the queue, and starts to dequeue the nodes in the order that they were added, analyzing those successors and adding them to the queue as well. This method of searching through a graph expands all nodes as it searches, and therefore it can be fairly inefficient if the goal is very far from the root node. However, tracing the path from root to goal is much easier using this search method. | Breadth-First Search (BFS) is a searching algorithm that utilizes the concepts involved with the queue data structure. BFS works by expanding all successors to a node before moving onto analyzing any of those successors. This is known as a first-in, first-out (FIFO) approach. As the search goes through the nodes, it analyzes which nodes are successors, and adds those nodes to the queue as they are found. Then, the search goes back to the queue, and starts to dequeue the nodes in the order that they were added, analyzing those successors and adding them to the queue as well. This method of searching through a graph expands all nodes as it searches, and therefore it can be fairly inefficient if the goal is very far from the root node. However, tracing the path from root to goal is much easier using this search method. | ||
| - | For a more visual overview of this searching method, reference the first-half of this tutorial: http://www.pdf-archive.com/ | + | For a more visual overview of this searching method, reference the first-half of {{dylanw:bfsdfstutorial.pdf|this document}}. |
| The algorithm for BFS works like this: | The algorithm for BFS works like this: | ||
breadth-first_search_and_depth-first_search.txt · Last modified: 2017/02/09 12:22 by dwallace