DASL Wiki

User Tools

Site Tools

Trace:
bfs_and_dfs_implementation_v2

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
bfs_and_dfs_implementation_v2 [2023/11/09 18:18] – [Depth First Search] fpalustrebfs_and_dfs_implementation_v2 [2023/11/13 09:56] (current) – fpalustre
Line 1: Line 1:
-====== BFS & DFS Implementation V2 (IN-PROGRSS) ======+====== BFS & DFS Implementation (2023) (IN-PROGRSS) ======
 **Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu> **Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu>
 \\ \\
-**Date:** Last modified on <11/09/23>+**Date:** Last modified on <11/13/23>
 \\ \\
 **Keywords:** Navigation, BFS, DFS, Robotino, cpp, **Keywords:** Navigation, BFS, DFS, Robotino, cpp,
Line 9: Line 9:
 {{ :sampleimageforwritingtutorial.jpg?200 |}} {{ :sampleimageforwritingtutorial.jpg?200 |}}
 \\ \\
-The photo above depicts <fill in the blank> which allows you to <fill in the blank>. The big picture problem is <fill in the blank>. Solving this partially or completely is important because <fill in the blank>. This tutorial shows you how to <fill in the blank> and takes approximately <fill in the blank> hours to complete. +The photo above depicts the environment used for travel which allows you to visually see the intended path that should be taken for Robotino . The big picture problem is understanding the traversal process and how it came to be. Solving this partially or completely is important because this gives robots an autonomous navigation process, limiting human interference. This tutorial shows you how to apply BFS and DFS to Robotino and should take approximately 1-2 hour to complete. 
 \\ \\
 ===== Motivation and Audience ===== ===== Motivation and Audience =====
-This tutorial's motivation is to find ways for robots to autonomously navigate their environments. Readers of this tutorial assumes the reader has the following background and interests: +This tutorial's motivation is to find ways for robots to autonomously navigate within their environments. Readers of this tutorial assumes the reader has the following background and interests: 
  
 <fc blue>   <fc blue>  
Line 21: Line 21:
   * Know how to navigate within the terminal in Linux   * Know how to navigate within the terminal in Linux
 \\ \\
-  * This tutorial may also attract readers who are interesting in implementing algorithms in their own projects+  * This tutorial may also attract readers who are interested in implementing algorithms in their own projects
 </fc> </fc>
 \\ \\  \\ \\ 
Line 179: Line 179:
     }     }
 ==== Breadth First Search==== ==== Breadth First Search====
 + {{ youtube>GH0YCbQobio?large }}
 Algorithm for BFS Algorithm for BFS
  
Line 213: Line 214:
               }               }
           }           }
 +          //if no path, return empty vector
           return vector<string>();           return vector<string>();
     }     }
Line 220: Line 222:
 \\ \\
 There are two ways to traverse in DFS, an iterative approach and recursive approach. The following is a recursive approach because it is the most common. In the source code, there will be iterative as well. There are two ways to traverse in DFS, an iterative approach and recursive approach. The following is a recursive approach because it is the most common. In the source code, there will be iterative as well.
 +
 +
 +    vector<string> DFS(map<string, vector<string> > &graph, const string &startingNode, const string &desiredNode, map<string, bool> &visited) {
 +         //mark the current node as visited
 +         visited[startingNode] = true;
 +         
 +         //containers of current path
 +         vector<string> path;
 +         
 +         //get adjacent nodes of starting node
 +         vector<string> adjNodes = graph[startingNode];
 +         
 +         //iterate through adjacent nodes
 +         for ( vector<string>::iterator it = adjNodes.begin(); it != adjNodes.end(); it++) {
 +             const string& nextNode = *adjNodes;
 +             
 +              //check if next node has been visited
 +              if (!visited[nextNode]) {
 +                 //recursively call DFS on the next node
 +                  vector<string> subPath = DFS(graph, nextNode, desiredNode, visited);
 +                  
 +                  //if subPath not empty, path to desired node is found
 +                  if (!subPath.empty()) {
 +                     //insert current node at beginning of subPath and return final path
 +                     subPath.insert(subPath.begin(), startingNode);
 +                     return subPath;
 +                  }
 +              }
 +          }
 +          //if no path, return empty vector
 +          return vector<string>();
 +    }
 +
 ==== Final Words ==== ==== Final Words ====
  
Line 225: Line 260:
 \\ \\
 \\ \\
-Speculating future work derived from this tutorial, includes <fill in the blank>. In the big picture, the problem of <fill in the blank> can be solved with this tutorial.+Speculating future work derived from this tutorial, includes applying these and other algorithms such as Dijkstra and A* to Robotino and other robots. In the big picture, the problem of autonomous navigation can be solved with this tutorial.
 \\ \\
 \\ \\
bfs_and_dfs_implementation_v2.1699582686.txt.gz · Last modified: by fpalustre