# Lab 10

Today we will learn about breadth first search (BFS) and how it can be used to find shortest paths in a graph. We start with Graph.java, which initializes a graph where the nodes are New England states (represented by Strings), and two states are connected by an edge if they share a border. The graph is stored using an adjacency list representation: each node is linked to the set of its neighbors. This representation is more efficient than the adjacency matrix because typically the number of edges is linear in the number of vertices, so there is no need to use a matrix with n^2 entries when only O(n) of them will be used.

More specifically, the graph is stored in this datastructure:

HashMap<String, HashSet<String>> graph = new HashMap<String, HashSet<String>>();

Calling graph.get(node) returns the set of all vertices adjacent to node.

Your task today is to imlement a breadth-first search on this graph to find the shortest path between "Maine" and "Rhode Island." You may already know about breadth-first search if you did the exercise that visits the nodes of a tree in level-order: the idea is to first visit all nodes that are one link away, then visit all nodes that are two links away, and so on.

In addition, each time we "discover" a vertex we can keep track of the node that it was discovered from, which we call its parent. You can see that this procedure will give us shortest paths in a graph that is unweighted: if we run a BFS from u we will find all vertices v reachable from u, and we can "backtrack" from each node v (by using the parent information) to find the shortest path between u and v.

To implement BFS you will need a queue of vertices, a way to mark vertices that have been visited, and a way to "remember" the parent of each vertex that is discovered. You will see that the necessary objects have already been initialized for you: