Graphs, Recursive Backtracking, and Priority Queues

April 17, 2013

Snarf the code for today's class from the InClass folder.

Graphs and Recursive Backtracking

Open the file GraphSearch.java. You will be writing a recursive backtracking function to determine if there is a path in the graph starting at vertex x that sums to a value. The graph is defined as a String array, where vertex x is connected to the vertices in index x. For example: given the input {"1 2", "0", "0"}, implies that vertex 0 is connected to vertices 1 and 2, and vertices 1 and 2 are connected to vertex 0.

You need to complete the function dfs that uses a depth-first search to find if a path the sums to the target value exists in the graph. Follow the comments.

Dijkstra's Algorithm and Priority Queues

First, read through Dijkstra's algorithm on Wikipedia.

Open Graph.java. In this code, the graph is saved in a 2x2 matrix such that the weight connecting nodes i and j is located at i,j. Look through the code and make sure you understand this before beginning to code Dijkstra's algorithm.

The comments in the code will walk you through the algorithm and help you with your code.

Submit your code from today's class in the April17 folder.