User Tools

Site Tools


breadth-first_search_and_depth-first_search

This is an old revision of the document!


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.

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/.

To learn or refresh your knowledge of linked lists, here is a great tutorial for these concepts: http://www.cprogramming.com/tutorial/lesson15.html.

For stacks, I prefer to reference this video: https://www.youtube.com/watch?v=UTgOWWmOVXY.

For queues, I prefer to reference this video: https://www.youtube.com/watch?v=JmQWuEnual4.

To learn about graph trees, here is a great tutorial for these concepts: http://www.tutorialspoint.com/graph_theory/index.htm.

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/2016/05/24/bfsdfstutorial/.

The algorithm for BFS works like this:

1. Put the root node or starting node on queue (s).
2. Examine the queue, whether it is empty or not.

a) If the queue is void, return the failure and stop the searching process.
b) Else, proceed ahead by placing the direct child nodes that have not been discovered yet.

3. If the goal node (g) is found as the first element of the queue, return it as success and stop.
4. Otherwise, removal and expansion of the first element of the queue is required. Place these newly generated offspring at the end of queue at any order.
5. Go back to the step 2 and repeat.

Imagine a graph like this:

This graph will be used for our code example.

BFS Code (w/ comments)

  #include <iostream>
  #include <ctime>
  using namespace std;
  
  struct node //the data structure for the nodes that are being explored
  {
      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:
          Queue()
          {
              front = NULL;
              rear = NULL;
          }
          ~Queue()
          {
              delete front;
          }
          void display() //displays the nodes stored within the queue
          {
              node *p = new node();
              p = front;
              if(front == NULL)
                  cout << "\nNothing to display!" << endl;
              else
              {
                  while(p != NULL)
                  {
                      cout << "\n" << p->data << endl;
                      p = p->next;
                  }
              }
          }
          void enqueue(int indata) //adds a new node to the queue
          {
              node *temp = new node();
              temp->data = indata;
              temp->next = NULL;
              if(front == NULL)
                  front = temp;
              else
                  rear->next = temp;
              rear = temp;
          }
          int dequeue() //removes a node from the queue and returns the value of that node
          {
              node *temp = new node();
              int tempdata;
              if(front == NULL)
                  cout << "\nQueue is empty!" << endl;
              else
              {
                  temp = front;
                  tempdata = temp->data;
                  front = front->next;
                  delete temp;
              }
              return tempdata;
          }
          bool isEmpty() //denotes whether the queue is empty or not
          {
              return (front == NULL);
          }
  };
  class Graph //the data structure for the graph that is to be searched through
  {
      private:
          int n; //# of vertices in graph
          int **A; //stores the edge between two vertices
      public:
          Graph(int size) //allows for variable creation of intital nodes
          {
              if(size < 2)
                  n = 2;
              else
                  n = size;
              A = new int*[n];
              for(int i = 0; i < n; i++)
                  A[i] = new int[n];
              for(int j = 0; j < n; j++)
                  for(int k = 0; k < n; k++)
                      A[j][k] = 0;
          }
          ~Graph()
          {
              for(int i = 0; i < n; i++)
                  delete [] A[i];
              delete [] A;
          }
          bool isConnected(int u, int v) //denotes is the two nodes being checked are connected to each other in the graph
          {
              return (A[u-1][v-1] == 1);
          }
          void addEdge(int u, int v) //adds a connection between the two given nodes
          {
              A[u-1][v-1] = A[v-1][u-1] = 1;
          }
          void BFS(int s, int g) //the Breadth-First Search function for searching through the graph
          {
              Queue Q;
              bool found = false;
              bool *explored = new bool[n+1]; //stores explored vertices
              for(int i = 1; i <= n; i++) //initializes all vertices as unexplored
                  explored[i] = false;
              Q.enqueue(s); //adds intial vertex
              explored[s] = true;
              cout << "BFS starting from vertex " << s << endl;
              while(!Q.isEmpty() && !found)
              {
                  int v = Q.dequeue();
                  cout << v << " ";
                  if(v == g) //stop the search after the goal node has been found
                  {
                      cout << "\n\nGoal found.";
                      found = true;
                  }
                  else
                  {
                      for(int w = 1; w <= n; w++)
                      {
                          if(isConnected(v, w) && !explored[w]) //enqueues the nodes that are connected to each other, in a FIFO order
                          {
                              Q.enqueue(w);
                              explored[w] = true;
                          }
                      }
                  }
              }
              cout << endl;
              delete [] explored;
          }
  };
  int main()
  {
      Graph g(12);
      g.addEdge(1, 2);
      g.addEdge(1, 3);
      g.addEdge(2, 4);
      g.addEdge(3, 4);
      g.addEdge(3, 6);
      g.addEdge(4, 7);
      g.addEdge(5, 6);
      g.addEdge(5, 7);
      clock_t t1;
      t1 = clock();
      g.BFS(1, 3);
      float diff = (double)(clock() - t1)/CLOCKS_PER_SEC;
      cout << endl << "Time taken for BFS: " << diff << endl;
      return 0;
  }

Depth-First Search (DFS) works off of the same graph theory that is used to approach BFS, however it takes a different approach to how it searches through each node. Instead of utilizing a queue data structure to store the nodes that need to be analyzed, DFS uses the stack data structure to search through a graph of vertices. With this method of searching, DFS takes what is known as a Last-In, First-Out (LIFO) searching method. This makes DFS search downward through the levels of nodes, instead of expanding through each level, it expands on the last node that was analyzed. This gives DFS the advantage of often finding the goal much faster and with less processing than BFS. However, this can cause problems when determining the path to take to the goal, as the path taken through DFS may not always be the fastest path to the goal.

For a more visual overview of this searching method, reference the second-half of this tutorial: http://www.pdf-archive.com/2016/05/24/bfsdfstutorial/.

The algorithm for DFS works like this:

1. Put root node (x) on the top of the stack.
2. Examine whether the stack is empty or not.

a) If the stack is found to be void, return the failure and stop.\\ 
b) Else proceed forward.\\ 

3. If the first element of the stack is the searched or goal node (g), return it as success.
4. Otherwise, proceed ahead with expansion and removal of first element. The chgildren of first element should be placed at the top of stack.
5. Go back to step 2.

The same graph used in the BFS example will be used for our code example.

DFS Code(w/ comments)

  #include <iostream>
  #include <ctime>
  #include <malloc.h>
  using namespace std;
  struct node //the data structure fopr the nodes that are being explored
  {
      int data;
      struct node *next;
  };
  class stack //the data structure for the queue that is being used to store the nodes that are being searched
  {
      private:
          struct node *top;
      public:
          stack()
          {
              top = NULL;
          }
          void push(int indata) //pushes a node onto the stack
          {
              node *p;
              if((p=(node*)malloc(sizeof(node))) == NULL)
              {
                  cout<<"Memory Exhausted";
                  exit(0);
              }
              p = new node;
              p->data = indata;
              p->next = NULL;
              if(top != NULL)
              {
                  p->next = top;
              }
              top = p;
          }
          int pop() //pops a node from the top of the stack
          {
              struct node *temp;
              int value;
              if(top == NULL)
              {
                  cout << "\nThe stack is Empty" << endl;
              }
              else
              {
                  temp = top;
                  top = top->next;
                  value = temp->data;
                  delete temp;
              }
              return value;
          }
          bool isEmpty() //denotes whether the stack is empty
          {
              return (top == NULL);
          }
          void display() //displays the nodes and their order in the stack
          {
              struct node *p = top;
              if(top == NULL)
              {
                  cout << "\nNothing to Display\n";
              }
              else
              {
                  cout << "\n The contents of stack\n";
                  while(p != NULL)
                  {
                      cout << p->data << endl;
                      p = p->next;
                  }
              }
          }
  };
  class Graph
  {
      private:
          int n;
          int **A;
      public:
          Graph(int size) //allows for variable creation of graph sizes
          {
              int i, j;
              if (size < 2)
                  n = 2;
              else
                  n = size;
              A = new int*[n];
              for (i = 0; i < n; ++i)
                  A[i] = new int[n];
              for (i = 0; i < n; ++i)
                  for (j = 0; j < n; ++j)
                      A[i][j] = 0;
          }
          ~Graph()
          {
              for (int i = 0; i < n; ++i)
              delete [] A[i];
              delete [] A;
          }
          bool isConnected(int x, int y) //denotes whether two nodes are connected to each other
          {
              return (A[x-1][y-1] == 1);
          }
          void addEdge(int x, int y) //adds an edge connecting the two given nodes
          {
              A[x-1][y-1] = A[y-1][x-1] = 1;
          }
          void DFS(int x, int g) //the function for the Depth-First Search
          {
              stack s;
              bool *explored = new bool[n+1]; //stores explored nodes
              bool found = false;
              int i;
              for(i = 0; i <= n; i++) //initializes all nodes as not explored
                  explored[i] = false;
              s.push(x); //adds the initial node
              explored[x] = true;
              cout << "Depth first Search starting from vertex ";
              cout << x << " : " << endl;
              while(!s.isEmpty() && !found)
              {
                  int k = s.pop();
                  cout << k << " ";
                  if(k == g) //stops the search after the goal node has been found
                  {
                      cout << "\n\nGoal found!";
                      found = true;
                  }
                  else
                  {
                      for (i = n; i >= 0 ; i--) //push the nodes that are connected to each other, in LILO order
                          if(isConnected(k, i) && !explored[i])
                          {
                              s.push(i);
                              explored[i] = true;
                          }
                  }
              }
              cout << endl;
              delete [] explored;
          }
  };
  int main()
  {
      Graph g(8);
      g.addEdge(1, 2);
      g.addEdge(1, 3);
      g.addEdge(1, 4);
      g.addEdge(2, 5);
      g.addEdge(2, 6);
      g.addEdge(4, 7);
      g.addEdge(4, 8);
      clock_t t1;
      t1 = clock();
      g.DFS(1, 4);
      float diff = (double)(clock() - t1)/CLOCKS_PER_SEC;
      cout << endl << "Time taken for DFS: " << diff << endl;
      return 0;
  }

Conclusion

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