3 Blind search algorithms
This chapter covers
- Applying different graph types
- Graph search algorithms
- Using graph traversal algorithms to find a path between two nodes
- Using blind search algorithms to find the shortest path between two nodes in a graph
- Solving a real-world routing problem using graph search algorithms
You were introduced to deterministic and stochastic algorithms in chapter 2. In this chapter, we will focus on deterministic algorithms, specifically blind search algorithms, and their applications in exploring tree or graph structures and finding the shortest path between nodes. Using these algorithms, you can explore a maze from an initial state to a goal state, solve n-puzzle problems, figure out the distance between you and any other person on a social media graph, search a family tree to determine the exact relationship between any two related people, or find the shortest path between any origin (e.g., your home) and any destination. Blind search algorithms are important, as they are often more efficient and practical to use when dealing with simple, well-defined problems.
3.1 Introduction to graphs
A graph is a nonlinear data structure composed of entities known as vertices (or nodes) and the relationships between them, known as edges (or arcs or links). This data structure does not follow a sequential pattern, making it nonlinear, unlike arrays, stacks, or queues, which are linear structures.