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: LinkedList<String> queue = new LinkedList<String>(); HashSet<String> visited = new HashSet<String>(); HashMap<String, String> parents = new HashMap<String, String>(); Now you just need to implement the breadth-first search itself. You should start by adding the starting vertex to the queue and marking it as visited. You then iteratively repeat the following procedure. Each time you remove a vertex v from the head of the queue, and look at its neighbors N(v). For each node in N(v) that has not been discovered mark it as visited, set its parent to v, and add it to the back of the queue. Your procedure stops when there are no more vertices in the queue. Remember that vertices need to be marked as discovered when they are enqueued (and not when they are dequeued). Once you run BFS starting from "Maine," to get a shortest path between "Maine" and "Rhode Island" you just need to backtrack from "Rhode Island" using the parents map, which will give you the vertices on a shortest path in reverse order. Please save your work in a directory called lab10 and submit it when you are done.

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:

LinkedList<String> queue = new LinkedList<String>();
HashSet<String> visited = new HashSet<String>();
HashMap<String, String> parents = new HashMap<String, String>();

Now you just need to implement the breadth-first search itself. You should start by adding the starting vertex to the queue and marking it as visited. You then iteratively repeat the following procedure. Each time you remove a vertex v from the head of the queue, and look at its neighbors N(v). For each node in N(v) that has not been discovered mark it as visited, set its parent to v, and add it to the back of the queue. Your procedure stops when there are no more vertices in the queue. Remember that vertices need to be marked as discovered when they are enqueued (and not when they are dequeued).

Once you run BFS starting from "Maine," to get a shortest path between "Maine" and "Rhode Island" you just need to backtrack from "Rhode Island" using the parents map, which will give you the vertices on a shortest path in reverse order.

Please save your work in a directory called lab10 and submit it when you are done.