Breadth-first search (BFS) is an algorithm that allows finding the shortest distance between 2 things.

BFS use cases: write an AI that calculates the fewest moves to victory in chess, write a spell checker and find the closest doctor to you on your social network.

Suppose you are in point A, and want to get to point D with the minimal number of transfers. There are multiple paths you could take. To do that, you check between the nodes if any could take you to D directly. If not, you see the options available on the next nodes checking if any could take you to D directly. You keep doing that until you reach D. That problem’s name is “shortest-path”, and you use BFS to solve it.

You solve a problem with BFS on 2 steps: . Model the problem as a graph . Solve the problem using BFS

A graph models a set of connections.

A graph is made up of nodes and edges. The edges are the lines that connect the nodes.

BFS runs on graphs. It helps answer 2 questions: . Is there a path from node A to B? . What is the shortest path from node A to node B?

Suppose you want to know if you have a dentist on your social network. BFS allows you to do so. The algorithm to do that is: . Make a list of close friends to search . Go to each one on the list and check if s/he is a dentist. . If not, for each friend, check on his network if there is a dentist. . If there is not a dentist on your friends’ network, go to their friends and check for friends of their also. On that algorithm, the first-degree connections are searched before the second-degree connections, second-degree are searched before third-degree and so on.

BFS not only finds the path from A to B, but also the shortest path.

If you e.g. need to search for people with BFS, you need to search them in the order that they are added. To do that, you will use the queue data structure.

Queues work as on real life.

You can’t access random elements on a queue.

There are only 2 operations on a queue: enqueue and dequeue.

Queue is a FIFO data structure: First In, First Out.

Stack is a LIFO data structure: Last In, First Out.

Once you search a node, you must mark that node as searched, to not search it again and end up in an infinite loop.

You need to check nodes in the order they were added to the search list - that means the search list must be a queue. That is the only way to get the shortest path.

The Big-O notation for the Breadth-first search is O(V+E) - which means number of nodes (vertices) + number of edges.

A directed graph has arrows, and the relationships follows the direction of the arrow.

Undirected graphs do not have arrows, and the relationship goes both ways.

A tree is a special kind of graph, where the edges do not point back (a directed graph).