depth-first

Depth-first Search (DFS)

Introduction

A depth-first search (DFS) algorithm explores graph or tree structures by traversing down one branch as far as possible before backtracking. This strategy entails managing the frontier, which is the set of nodes that are yet to be explored. In DFS, the frontier is typically handled using a stack data structure, adhering to the "last-in, first-out" (LIFO) principle.

Usage

python maze.py maze.txt

Examples

Maze 1

Solution 1

States Explored: 17

Maze 2

Solution 2

States Explored: 194

Maze 3

Solution 3

States Explored: 483

References

• CS50’s Introduction to Artificial Intelligence with Python