User Tools

Site Tools


breadth-first_search_and_depth-first_search

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
breadth-first_search_and_depth-first_search [2016/07/16 21:49] dwallacebreadth-first_search_and_depth-first_search [2017/02/09 12:22] (current) dwallace
Line 1: Line 1:
 =====Introduction===== =====Introduction=====
  
-This tutorial serves as an introduction to path-planning and search algorithms. However, these topics do require prior knowledge of the methods used to program these algorithms. In order to understand these tutorials, you will need to be comfortable with C++, and especially the concepts associated with linked lists, stacks, and queues. An understanding of graph trees and how they are searched is also helpful for these tutorials.+This tutorial serves as an introduction to path-planning and search algorithms. However, these topics do require prior knowledge of the methods used to program these algorithms. In order to understand these tutorials, you will need to be comfortable with Cpp, and especially the concepts associated with linked lists, stacks, and queues. An understanding of graph trees and how they are searched is also helpful for these tutorials.
  
-If you want to learn C++ before reading these tutorials, there are a wealth of tutorials on the internet, and many will have different learning impact depending on personal preference. Here is one that I found helpful when learning the basics of C++: http://www.cplusplus.com/doc/tutorial/.+If you want to learn Cpp before reading these tutorials, there are a wealth of tutorials on the internet, and many will have different learning impact depending on personal preference. Here is one that I found helpful when learning the basics of Cpp: http://www.cplusplus.com/doc/tutorial/.
  
 To learn or refresh your knowledge of linked lists, here is a great tutorial for these concepts: http://www.cprogramming.com/tutorial/lesson15.html. To learn or refresh your knowledge of linked lists, here is a great tutorial for these concepts: http://www.cprogramming.com/tutorial/lesson15.html.
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 tutorialhttp://www.pdf-archive.com/2016/05/24/bfsdfstutorial/.+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:
Line 35: Line 35:
  
 ===BFS Code (w/ comments)=== ===BFS Code (w/ comments)===
-<Code:c++ linenums:1>+<file c++ BFS.cpp>
 #include <iostream> #include <iostream>
 #include <ctime> #include <ctime>
Line 226: Line 226:
     return 0;     return 0;
 } }
-</Code>+</file>
 =====Depth-First Search===== =====Depth-First Search=====
  
Line 246: Line 246:
  
 ===DFS Code(w/ comments)=== ===DFS Code(w/ comments)===
-<Code:c++linenums:1>+<file c++ DFS.cpp>
 #include <iostream> #include <iostream>
 #include <ctime> #include <ctime>
Line 439: Line 439:
     return 0;     return 0;
 } }
-</Code>+</file>
  
 =====Final Words===== =====Final Words=====
breadth-first_search_and_depth-first_search.1468730974.txt.gz · Last modified: 2016/07/16 21:49 by dwallace