📄️ 5.1 Algorithm Explanation
Depth First Search (DFS) and Breadth First Search (BFS) are two of the most common priority search methods. They are widely used for searching in structures such as graphs and trees.
📄️ 5.2 Depth First Search
Depth First Search (DFS) is a search method where, upon encountering a new node, you immediately traverse that new node. Therefore, traversal requires a Last In, First Out (LIFO) stack, which can also be implemented using recursion, equivalent to using a stack. In a tree structure, since traversal always invokes the new node, it appears as if progressing in the "depth" direction. In Python, collections.deque can be used to implement the stack in C++. However, in most cases, using vector in C++ or list in Python is preferred as these structures not only support LIFO but also allow random access.
📄️ 5.3 Backtracking
Backtracking is a special case of priority search, also known as the trial-and-error method. It is commonly used in depth-first search when the state of nodes needs to be recorded. Typically, problems involving permutations, combinations, or selections are more conveniently solved using backtracking.
📄️ 5.4 Breadth-First Search
Breadth-First Search (BFS) differs from Depth-First Search in that it traverses level by level, so it requires a first-in, first-out queue instead of the last-in, first-out stack used in DFS. Since BFS processes nodes by levels, it explores nodes in a "broad" manner and is often used for solving shortest path problems. In Python, we can use collections.deque to implement the queue used in C++.
📄️ 5.5 Exercises
Basic Difficulty