Answer to Question #159100 in C++ for Eeshal

Question

Scenario: 

Your friend is developing a maze puzzle game and already designed a module which can generate a random maze. The maze has one entry and one exit point. Now he needs to develop the module which will find the path from entry to exit points for randomly generated maze. Your friend wants the path searching should be quickest. He can use only Stack or Queue data structures to store maze’s visited locations for path generation. He is unable to decide the selection of data structure and asked you to help him.

Question: 

From Stack and Queue data structures which data structure you will suggest using for entry to exit path finding module? Select a data structure and give comments in favour to justify your selection. Also mention why you are not selecting the other data structure?

Answer 1

DFS (Depth-First Search) and BFS (Breadth-First Search) are two main algorithms that we can choose from in this case. It should be mentioned that stack is used by DFS and queue is used by BFS.

Our main selection criterion for searching is for it to be quick. As a result, we should avoid BFS (queue), because it goes through every possible path and finds the shortest one. So, we will use DFS (stack) - it will also save us more memory and might be easier to implement.