## 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 More specifically, the graph is stored in this datastructure:
Calling 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 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>(); 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 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. |