As you know, LinkedIn is a social network, and users are connected to one another through first- or second-degree connections. In order to better understand this concept, use the following diagram as a reference:

Suppose that I want to find an acquaintance named Jill and connect with her. When I go to her profile, I find that she is a second-degree connection, which means that we have a mutual colleague. Let's look at how this degree is computed. To do so, we will create a connection tree:

1. We start with the profile node, Dev, and add it to the connection tree:

2. Now, I will find my colleagues and add them beneath my node. So, I add Ali and Tom beneath the Dev node:

3. Now, for both Ali and Tom, I find their colleagues and add them beneath their nodes. So, under Ali, I add Dev, Seth, and Ram, and under...

A graph is a non-linear data structure containing a set of points known as nodes (or vertices) and a set of links known as edges, as illustrated in the following diagram:

An edge that connects to the same node is called a cycle. As shown in the preceding diagram, nodes a and b are connected by two paths; one is through edge a-b, and the other is through edges a-d and d-b. A tree is a special type of graph, in which there are no cycles, and two nodes are connected by one path.

In Python, we can use a dictionary structure to represent a graph. A dictionary is a data structure where many keys are mapped to values. For a dictionary that represents a graph, the keys are the nodes, and the values of those nodes are the nodes that they are connected to:

In the preceding diagram, we can see that the following applies:

• For key a, the values are...

A queue is a sequence of people or objects waiting to be attended to. Some examples include a queue of people waiting at a counter, a queue of swimmers that are ready to dive in to a pool, and a queue of songs in a playlist:

Just like in a stack, there are two types of operations—one for inserting items into a queue, and one for removing items from a queue. When a person joins a queue, he or she must stand behind the last person. The operation of adding an item to a queue is called enqueue. The first person to be attended to in a queue is the person standing in the front. The operation to remove an item from a queue is called dequeue. Queue operations can be seen in the following diagram:

Since the first object inserted is the first one to be removed, this data structure is called first in first out (FIFO). In Python, we can use...

In this section, we'll look at the flow of the BFS algorithm, how a queue is used, and how graph data affects the algorithm. The flow of the BFS algorithm is similar to that of DFS, but instead of using a stack data structure, a queue data structure is used.

A flowchart of the BFS algorithm can be illustrated as follows:

1. We initially create a root node with an initial state, and add it to a queue and tree.
2. A node is dequeued from the queue, and we check whether it has the goal state. If it does, we end our search. If it doesn't, we find the child nodes of the dequeued node and add them to the queue entry.
3. This process is repeated until we either find the goal state or have exhausted all of the nodes in our search tree.
4. Since our connection data is in a graph structure, we have to check whether each node has been visited before.
5. So, we add...

In this section, we'll look at the differences between the DFS and BFS algorithms. We will compare these differences in terms of various factors.

In DFS, preference is given to child nodes, which means that after node a and node b are explored, and after node b and node c are explored, we hit a dead end and we backtrack to the previous level. This means that we go back to node b, and then to its next child, which is node c.

In BFS, the nodes are covered level by level, and preference is given to siblings. This means that after node a, nodes b and e are explored, and after that, nodes c, d, and f are explored, as indicated by the following diagram:

In the previous section, we discussed the differences between the DFS and BFS algorithms. In this section, we'll look at an application that you can try to develop yourself. We'll go over the application that you'll try to develop, and the changes that are required for the application.

Your aim will be to develop a university navigation application, as shown in the following diagram:

Suppose that this is the layout of the university, and people can travel along horizontal or vertical lines. In this application, the user has to enter the source and destination places. For this specific case, we'll assume that a new student wants to find his way from the Bus Stop to the AI Lab.

You can refer to the classes that we developed for the LinkedIn connection feature, as follows:

To adapt that code for this application, we need to...

In this chapter, to help you understand the BFS algorithm, we revisited the concepts of state and node. You learned about the graph and queue data structures, and we discussed the differences between the DFS and BFS algorithms.

In the next chapter, you'll be learning about the heuristic search algorithm. Instead of giving preference to child or sibling nodes, this method gives preference to the nodes that are closest to the goal state; the term heuristic refers to the measure of how close the nodes are to the goal state.