C++ Graph Search

This project is a C++ implementation of a graph and a graph search algorithm. As a reminder, a graph is a representation of entities that are related to each other in some way. The graph that I created uses an adjacency list to store 'edges', with each edge connecting two nodes.

Above is a generalized, abstarct Graph class that I created. It implements some functionality, such as the power to add edges to the graph and print the graph, but leaves a lot of the functinality (such as running algorithms) to be created when making a derived class. It is also worth mentioning that this class accepts a data type as a template parameter, meaning this graph can store any kind of data (including user defined types).

Using the generalized Graph class as a base, I created a derived graph_maze class. This class is intended to use the Graph that I created in a useful, applicable way. On top of the methods inherited publicly from the base class, this derived class includes functions to load in a maze from a .txt file and to run a depth-first-search (DFS) algorithm.

This is the DFS algorithm that I created. It is implemented as a recursive function that adds a new call to the stack everytime a 'split' in the maze path is found. This is so that it may explore every available path from the start of the maze to the end of the maze. This function keeps track of the solution path through the maze as a STL linked list of nodes.

This output is an example of a maze being solved. The maze is printed, a DFS algorithm is run, a STL list of nodes (representing the solution to the maze) is generated, and then a solved maze is printed. The '*' is the start of the maze, the 'x' is the end of the maze, the '@' is a part of the available path, and the '+' represents a node that is part of the solution.

This code is available in its entirety on my GitHub at this link