breadth-first_search_and_depth-first_search
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
breadth-first_search_and_depth-first_search [2016/05/24 00:30] – dwallace | breadth-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:// | + | 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:// |
To learn or refresh your knowledge of linked lists, here is a great tutorial for these concepts: http:// | To learn or refresh your knowledge of linked lists, here is a great tutorial for these concepts: http:// | ||
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: | ||
Line 35: | Line 35: | ||
===BFS Code (w/ comments)=== | ===BFS Code (w/ comments)=== | ||
+ | <file c++ BFS.cpp> | ||
+ | #include < | ||
+ | #include < | ||
+ | using namespace std; | ||
- | #include < | + | struct node //the data structure for the nodes that are being explored |
- | #include < | + | { |
- | using namespace std; | + | int data; |
- | + | node *next; | |
- | | + | }; |
- | { | + | |
- | int data; | + | |
- | node *next; | + | |
- | }; | + | |
- | + | ||
- | class Queue //the data structure for the queue that is being used to store the nodes that are being searched | + | |
- | { | + | |
- | private: | + | |
- | node *front; | + | |
- | node *rear; | + | |
- | public: | + | class Queue //the data structure for the queue that is being used to store the nodes that are being searched |
- | | + | { |
- | { | + | |
- | front = NULL; | + | node *front; |
- | rear = NULL; | + | node *rear; |
- | } | + | |
- | ~Queue() | + | public: |
- | { | + | |
- | | + | { |
- | } | + | front = NULL; |
+ | | ||
+ | | ||
- | | + | ~Queue() |
+ | { | ||
+ | delete front; | ||
+ | } | ||
+ | |||
+ | | ||
+ | { | ||
+ | node *p = new node(); | ||
+ | p = front; | ||
+ | if(front == NULL) | ||
+ | cout << " | ||
+ | |||
+ | else | ||
{ | { | ||
- | | + | |
- | | + | |
- | if(front == NULL) | + | |
- | cout << " | + | |
- | + | ||
- | else | + | |
{ | { | ||
- | | + | cout << " |
- | { | + | p = p->next; |
- | | + | |
- | p = p->next; | + | |
- | } | + | |
} | } | ||
} | } | ||
+ | } | ||
- | | + | |
- | { | + | { |
- | node *temp = new node(); | + | node *temp = new node(); |
- | temp-> | + | temp-> |
- | temp-> | + | temp-> |
- | if(front == NULL) | + | if(front == NULL) |
- | front = temp; | + | front = temp; |
- | | + | |
- | rear-> | + | rear-> |
- | | + | |
- | } | + | } |
- | | + | |
+ | { | ||
+ | node *temp = new node(); | ||
+ | int tempdata; | ||
+ | if(front == NULL) | ||
+ | cout << " | ||
+ | |||
+ | else | ||
{ | { | ||
- | | + | temp = front; |
- | | + | tempdata |
- | | + | front = front-> |
- | cout << " | + | |
+ | } | ||
- | else | + | return |
- | { | + | } |
- | temp = front; | + | |
- | | + | |
- | front = front-> | + | |
- | delete temp; | + | |
- | } | + | |
- | | + | bool isEmpty() //returns whether the queue is empty or not |
- | } | + | { |
+ | | ||
+ | } | ||
+ | }; | ||
- | bool isEmpty() | + | class Graph //the data structure for the graph that is to be searched through |
- | { | + | { |
- | | + | |
- | } | + | int n; //# of vertices in graph |
- | }; | + | int **A; //stores the edge between two vertices |
- | | + | |
- | { | + | |
- | | + | { |
- | | + | |
- | int **A; //stores the edge between two vertices | + | n = 2; |
- | public: | + | else |
- | Graph(int size) //allows for variable creation of intital nodes | + | n = size; |
- | { | + | |
- | | + | |
- | | + | |
- | else | + | A = new int*[n]; |
- | n = size; | + | |
+ | A[i] = new int[n]; | ||
- | A = new int*[n]; | + | for(int j = 0; j < n; j++) |
- | for(int | + | for(int |
- | A[i] = new int[n]; | + | A[j][k] = 0; |
+ | } | ||
- | for(int j = 0; j < n; j++) | + | ~Graph() |
- | for(int | + | { |
- | A[j][k] = 0; | + | |
- | } | + | |
- | | + | delete [] A; |
- | { | + | } |
- | for(int i = 0; i < n; i++) | + | |
- | | + | |
- | delete | + | bool isConnected(int u, int v) //returns whether the two nodes being checked are connected to each other in the graph |
- | } | + | { |
+ | return (A[u-1][v-1] == 1); | ||
+ | } | ||
- | bool isConnected(int u, int v) //denotes is the two nodes being checked are connected to each other in the graph | + | void addEdge(int u, int v) //adds a connection between |
- | { | + | { |
- | | + | A[u-1][v-1] = A[v-1][u-1] |
- | } | + | } |
- | | + | |
- | { | + | { |
- | | + | Queue Q; |
- | | + | |
- | | + | bool *explored |
- | { | + | |
- | Queue Q; | + | |
- | | + | |
- | bool *explored | + | for(int i = 1; i <= n; i++) //initializes all vertices |
+ | explored[i] = false; | ||
- | for(int i = 1; i <= n; i++) //initializes all vertices as unexplored | + | Q.enqueue(s); //adds intial vertex |
- | explored[i] = false; | + | explored[s] = true; |
+ | cout << "BFS starting from vertex " << s << endl; | ||
- | | + | while(!Q.isEmpty() && !found) |
- | | + | { |
- | cout << | + | |
+ | cout << | ||
- | | + | |
{ | { | ||
- | | + | cout << "\n\nGoal found."; |
- | | + | found = true; |
+ | } | ||
- | if(v == g) //stop the search after the goal node has been found | + | else |
- | { | + | { |
- | | + | |
- | found = true; | + | |
- | } | + | |
- | + | ||
- | else | + | |
{ | { | ||
- | | + | |
{ | { | ||
- | | + | Q.enqueue(w); |
- | { | + | explored[w] = true; |
- | | + | |
- | explored[w] = true; | + | |
- | } | + | |
} | } | ||
} | } | ||
} | } | ||
- | |||
- | cout << endl; | ||
- | delete [] explored; | ||
} | } | ||
- | }; | ||
- | int main() | + | cout << endl; |
- | { | + | |
- | | + | |
+ | }; | ||
- | g.addEdge(1, 2); | + | int main() |
- | | + | { |
- | g.addEdge(2, | + | |
- | g.addEdge(3, | + | |
- | g.addEdge(3, | + | |
- | g.addEdge(4, | + | |
- | g.addEdge(5, | + | |
- | g.addEdge(5, 7); | + | |
- | clock_t t1; | + | g.addEdge(1, |
- | t1 = clock(); | + | g.addEdge(1, |
+ | g.addEdge(2, | ||
+ | g.addEdge(3, | ||
+ | g.addEdge(3, | ||
+ | g.addEdge(4, | ||
+ | g.addEdge(5, | ||
+ | | ||
- | g.BFS(1, 3); | + | clock_t t1; |
- | float diff = (double)(clock() | + | |
- | cout << endl << "Time taken for BFS: " << diff << endl; | + | |
- | return 0; | + | g.BFS(1, 3); //both tyhe root node and the goal node can be changed |
- | | + | |
+ | cout << endl << "Time taken for BFS: " << diff << endl; | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
=====Depth-First Search===== | =====Depth-First Search===== | ||
Line 246: | Line 246: | ||
===DFS Code(w/ comments)=== | ===DFS Code(w/ comments)=== | ||
- | | + | <file c++ DFS.cpp> |
- | #include < | + | #include < |
- | #include < | + | #include < |
- | using namespace std; | + | #include < |
+ | using namespace std; | ||
- | | + | struct node //the data structure |
- | { | + | { |
- | int data; | + | int data; |
- | struct node *next; | + | struct node *next; |
- | }; | + | }; |
- | | + | class stack //the data structure for the queue that is being used to store the nodes that are being searched |
- | { | + | { |
- | private: | + | private: |
- | struct node *top; | + | struct node *top; |
- | | + | |
- | stack() | + | stack() |
+ | { | ||
+ | | ||
+ | } | ||
+ | |||
+ | void push(int indata) //pushes a node onto the top of the stack | ||
+ | { | ||
+ | node *p; | ||
+ | if((p=(node*)malloc(sizeof(node))) == NULL) | ||
{ | { | ||
- | | + | |
+ | exit(0); | ||
} | } | ||
- | | + | |
+ | p->data = indata; | ||
+ | p->next = NULL; | ||
+ | if(top != NULL) | ||
{ | { | ||
- | | + | p->next = top; |
- | if((p=(node*)malloc(sizeof(node))) == NULL) | + | } |
- | { | + | top = p; |
- | cout<<" | + | } |
- | exit(0); | + | |
- | } | + | |
- | p = new node; | + | int pop() //pops a node from the top of the stack |
- | | + | { |
- | | + | struct node *temp; |
- | if(top | + | int value; |
- | { | + | if(top |
- | p->next = top; | + | { |
- | | + | |
- | top = p; | + | |
} | } | ||
- | | + | |
{ | { | ||
- | | + | temp = top; |
- | | + | |
- | | + | |
- | | + | |
- | cout << "\nThe stack is Empty" << endl; | + | } |
- | } | + | return value; |
+ | } | ||
- | else | + | bool isEmpty() //returns whether the stack is empty |
- | { | + | { |
- | temp = top; | + | |
- | | + | } |
- | value = temp-> | + | |
- | | + | void display() //displays the nodes and their order in the stack |
- | | + | { |
- | | + | |
- | | + | |
- | | + | |
{ | { | ||
- | | + | |
} | } | ||
- | | + | |
{ | { | ||
- | | + | |
- | | + | |
{ | { | ||
- | cout << | + | cout << |
+ | p = p->next; | ||
} | } | ||
+ | } | ||
+ | } | ||
+ | }; | ||
- | else | + | class Graph //the data structure for the graph that contains the nodes and the edges between them |
- | { | + | { |
- | cout << "\n The contents of stack\n" | + | |
+ | int n; | ||
+ | int **A; | ||
- | while(p != NULL) | + | public: |
- | { | + | Graph(int size) //allows for variable creation of graph size |
- | cout << p->data << endl; | + | { |
- | p = p-> | + | int i, j; |
- | } | + | if (size < 2) |
- | | + | |
- | } | + | |
- | }; | + | |
- | class Graph | + | else |
- | { | + | n = size; |
- | private: | + | |
- | int n; | + | |
- | int **A; | + | |
- | public: | + | A = new int*[n]; |
- | Graph(int size) //allows for variable creation of graph sizes | + | |
- | { | + | |
- | int i, j; | + | |
- | if (size < 2) | + | |
- | | + | |
- | else | + | for (i = 0; i < n; ++i) |
- | | + | A[i] = new int[n]; |
- | A = new int*[n]; | + | for (i = 0; i < n; ++i) |
+ | for (j = 0; j < n; ++j) | ||
+ | A[i][j] = 0; | ||
+ | } | ||
- | | + | ~Graph() |
- | A[i] = new int[n]; | + | { |
+ | | ||
+ | | ||
+ | delete | ||
+ | } | ||
- | for (i = 0; i < n; ++i) | + | bool isConnected(int x, int y) //returns whether two nodes are connected to each other |
- | | + | { |
- | | + | return |
- | } | + | } |
- | ~Graph() | + | void addEdge(int x, int y) //adds an edge connecting the two given nodes |
- | { | + | { |
- | for (int i = 0; i < n; ++i) | + | A[x-1][y-1] = A[y-1][x-1] = 1; |
- | delete | + | } |
- | delete | + | |
- | } | + | |
- | bool isConnected(int x, int y) //denotes whether | + | void DFS(int x, int g) //the function used for the Depth-First Search |
- | | + | { |
- | | + | stack s; |
- | | + | bool *explored = new bool[n+1]; //stores explored nodes |
+ | bool found = false; | ||
+ | | ||
+ | for(i = 0; i <= n; i++) // | ||
+ | explored[i] = false; | ||
+ | s.push(x); //adds the initial node to the top of the stack | ||
+ | | ||
- | | + | |
- | | + | |
- | A[x-1][y-1] = A[y-1][x-1] = 1; | + | |
- | } | + | |
- | | + | |
{ | { | ||
- | | + | int k = s.pop(); |
- | bool *explored = new bool[n+1]; //stores explored nodes | + | |
- | bool found = false; | + | |
- | | + | |
- | for(i = 0; i <= n; i++) // | + | |
- | explored[i] = false; | + | |
- | | + | |
- | | + | |
- | cout << "Depth first Search starting from vertex | + | |
- | | + | { |
+ | | ||
+ | found = true; | ||
+ | | ||
- | | + | |
{ | { | ||
- | | + | for (i = n; i >= 0 ; i--) //pushes |
- | cout << k << " "; | + | if(isConnected(k, |
- | + | { | |
- | if(k == g) //stops the search after the goal node has been found | + | s.push(i); |
- | { | + | explored[i] = true; |
- | cout << " | + | } |
- | found = true; | + | |
- | } | + | |
- | + | ||
- | else | + | |
- | { | + | |
- | | + | |
- | if(isConnected(k, | + | |
- | { | + | |
- | s.push(i); | + | |
- | explored[i] = true; | + | |
- | } | + | |
- | | + | |
} | } | ||
- | cout << endl; | ||
- | delete [] explored; | ||
} | } | ||
+ | cout << endl; | ||
+ | delete [] explored; | ||
+ | } | ||
- | | + | }; |
- | | + | int main() |
- | { | + | { |
- | Graph g(8); | + | Graph g(8); //creates a graph with 8 nodes |
- | g.addEdge(1, | + | g.addEdge(1, |
- | g.addEdge(1, | + | g.addEdge(1, |
- | g.addEdge(1, | + | g.addEdge(1, |
- | g.addEdge(2, | + | g.addEdge(2, |
- | g.addEdge(2, | + | g.addEdge(2, |
- | g.addEdge(4, | + | g.addEdge(4, |
- | g.addEdge(4, | + | g.addEdge(4, |
- | | + | |
- | t1 = clock(); | + | t1 = clock(); |
- | | + | |
- | | + | |
- | cout << endl << "Time taken for DFS: " << diff << endl; | + | cout << endl << "Time taken for DFS: " << diff << endl; |
- | | + | |
- | } | + | } |
+ | </ | ||
- | =====Conclusion===== | + | =====Final Words===== |
Both Breadth-First Search and Depth-First Search are very important algorithms for searching through graphs, and are especially useful in implementing path planning on autonomous systems. They may not be the fastest searching algorithms, however they are very integral to the modern understanding of path planning and searching through large sets of data. For information on implementing these algorithms, see the implementation page for BFS and DFS under the Path Planning section of the wiki. | Both Breadth-First Search and Depth-First Search are very important algorithms for searching through graphs, and are especially useful in implementing path planning on autonomous systems. They may not be the fastest searching algorithms, however they are very integral to the modern understanding of path planning and searching through large sets of data. For information on implementing these algorithms, see the implementation page for BFS and DFS under the Path Planning section of the wiki. | ||
breadth-first_search_and_depth-first_search.1464075044.txt.gz · Last modified: 2016/05/24 00:30 by dwallace