Hi tokes-ga,
There are two keys to the solution. The first is, as you suggest,
recursion. The second is memoization, where we'll save computed
answers so we don't have to compute them again in the future.
Memoization is a programming trick that trades space (memory needed by
the program) for time (computation effort). This allows us to achieve
the O(n^2) time bound that you desire.
To grasp the recursion, observe that the longest path starting from
any particular vertex, v, is the maximum longest path starting from a
neighboring vertex v', plus the single step from v to v'.
Turning to the Java code, assume you have a Vertex class that
represents a single vertex in the graph. An array of each vertex's
neighbors is retrieved with the Vertex class's method:
public Vertex[] getNeighbors()
We'll put our code within a Graph class that contains a private
variable that is an array of Vertex objects. I imagine that you have
already written these classes with similar methods, along with code
for initializing them. Then we can write the following code:
public class Graph {
import java.util.*;
private Vertex[] vertices;
// your constructor and initialization code goes here. it will
// initialize the vertices array.
// the public method that looks for the longest path starting
// from each vertex in the graph
public LinkedList findLongestPath() {
LinkedList longestPath = null;
Hashtable memo = new Hashtable();
for (int i = 0; i < vertices.length; i++) {
LinkedList tmpPath = findLongestPathFromVertex(vertices[i], memo);
if ((longestPath = null) ||
(tmpPath.size() > longestPath.size())) {
longestPath = tmpPath;
}
}
return longestPath;
}
// a recursive function to find the longest path from a
// particular vertex in the graph.
private LinkedList findLongestPathFromVertex(Vertex v, Hashtable memo) {
// we might have already computed the answer
LinkedList longestPath = (LinkedList) memo.get(v);
// if we didn't, we'll compute it now
if (longestPath == null) {
LinkedList longestNeighborPath = null;
Vertex[] neighbors = v.getneighbors();
for (int i = 0; i < neighbors.length; i++) {
// this is the recursive step
LinkedList tmpPath = findLongestPathFromVertex(neighbors[i], memo);
// we only want to keep the maximum longest neighbor path
if ((longestNeighborPath == null) ||
(tmpPath.size() > longestNeighborPath.size())) {
longestNeighborPath = tmpPath;
}
}
if (longestNeighborPath != null) {
longestPath = longestNeighborPath.clone();
}
else {
// this covers the case for when there are no neighbors
longestPath = new LinkedList();
}
// here we add the current vertex to the longest path at a neighbor
longestPath.addFirst(v);
// and we record the result, which is the second key, memoization
memo.put(v, longestPath);
}
return longestPath;
}
}
I hope this answers your question.
Sincerely,
dogbite-ga
Google Answers Researcher |