Breadth-First Search is an algorithm to search graph to find the shortest distance between two things.
In order to talk about breadth-first search we need to know what is a graph? and what do we mean by shortest path? So first, let's figure out what is a graph.
Graph
It is a model for a set of connections.
For Example, you are heading to many places today and you want to draw a graph to the places you would pass by, you will go from home to work, then to a restaurant, then you go back home, after that you would go to the supermarket.
Graphs are made of nodes and edges. A node can be directly connected to other nodes through edges. The directly connected nodes are called neighbors. In the above graph home is directly connected to work, so they are neighbors but work isn't directly connected to supermarket.
graphs are a way to model how different things are connected to one another.
Now let's talk about what is meant by shortest-path.
Shortest-Path
It is an algorithm to find the path with the fewest steps. consider the path from your house to your friends house, ask yourself can you do it in one step? if no can you do it in two steps? keep asking until you find the shortest path.
So in shortest path algorithms we follow two steps:
- Model the problem as a graph.
- Solve the problem using breadth-first search.😉
It is time to talk about breadth-first search.
Breadth-First Search
It is an algorithm that runs on a graph. It helps in answering two questions:
- Is there a path from node A to node B?
- What is the shortest path from node A to node B?
let's have an example to understand breadth-first more.
Suppose you are a new cat parent and you want to take your cat to a vet to make a checkup but you don't know any vet yet. Yo decided to have a look in your Facebook friends list to know if you are having a vet in your list.
- First, you will make a list of your friends to search.
- second, go to each person on the list and check whether that person is vet. If the person is a vet CONGRATULATIONS you are done. If not go to the next person in the list.
Suppose none of your friends are vet. Now you have to search through your friends' friends. so you need to connect every friend of your friends with a list of their friends and start searching the new list. while doing this process you have created a graph of connected people and preformed a search algorithm to find a vet.
In the previous process we saw how breadth-first search answers the first question. Is there a vet in my network?
Now let's try to answer the second question who is the closest vet? Your friends are 1st degree connections and their friends are 2nd degree, so it is preferred to find vet in your 1st degree connections. While forming a list of connections it is preferred to use a QUEUE to make sure that people are searched in the order you added them.
Breadth-First Search Usage
Here are some examples where breadth-first search is used:
- AI checkers that calculates the fewest moves to victory.
- Spell checker (fewest edits for the misspelled words).
Top comments (1)
great