1. Graph algorithms
Great job! I hope you had a ton of fun with those exercises. We're now going to take a small detour from node importance and look at a related concept: path-finding.
2. Finding paths
Path-finding has many important applications. One example is optimization problems, such as finding the shortest transportation path between two nodes. It's also important in modeling the spread of things, such as the spread of disease in an outbreak, or information spread in a social network. How do we find out whether there's a path between two nodes? If there's a path, how do we find out what the shortest path is? One way we can do so is by the "breadth-first-search algorithm".
3. Breadth-first search (BFS)
The breadth-first search algorithm was first developed in the 1950s as a way of finding the shortest path out of a maze. How does this algorithm work? Suppose we have the network above, comprised of 11 nodes, and we want to find the shortest path between the yellow and red nodes. The algorithm essentially works as such. If we start at the yellow node, we first ask for the yellow node's neighbors. We then ask
4. Breadth-first search (BFS)
if the destination node is present in the set of yellow node's neighbors. If not, we continue on. Going out a second degree of separation,
5. Breadth-first search (BFS)
we ask for the neighbors of our neighbors. The destination node is still not present, so we continue on.
6. Breadth-first search (BFS)
On our 3rd degree of separation out, we see that the destination node is present. At this point, we can stop and ignore the next degree of separation. Note that there was one other path possible, but it was longer. As such, with the breadth-first-search algorithm, we have achieved our goal of finding the "shortest" path between the pair of nodes. That is the breadth-first-search algorithm in its essence!
7. Recall: Neighbors
Let's quickly review some code that will help you with the following exercises. Say we have a graph G. As a good habit, let's check first for the number of nodes and edges present. Recall that we can do len(G-dot-edges) and len(G-dot-nodes), and see that there are 57 edges between 20 nodes. Let's see if we can find a path between nodes 1 and 19.
8. Recall: Neighbors
If we do G-dot-neighbors(1), we get back a list containing the nodes [10, 5, 14, 7] as the neighbors of 1. Let's go one degree out, to the first node in the list of node 1's neighbors, which is node 10. Now, let's check the neighbors of 10: note that we have 1, which is correct, and then 19, and then a whole slew of other nodes. Since 19, our destination node, is present in the neighbors of node 10, we can stop there. If 19 wasn't there, we would go on to check the neighbors of node 5, which was the next node in the list of node 1's neighbors.
9. Let's practice!
Just now, we had checked each neighbor manually. In the exercises, you will be implementing an automatic version of the breadth-first search algorithm. The exercises will also flex your algorithm-writing muscles, so go forth and have fun!