PathFinder.java
public class PathFinder
{
private ST prev = new ST();
private
ST dist = new ST();
public PathFinder(Graph G, String s
{
Queue q = new
Queue();
q.enqueue(s);
dist.put(s, 0);
while (!q.isEmpty())
{
String v = q.dequeue();
for (String w : G.adjacentTo(v))
{
if (!dist.contains(w))
{
q.enqueue(w);
dist.put(w, 1 +
dist.get(v));
prev.put(w, v);
}
}
}
}
public boolean isReachable(String v)
{
return dist.contains(v);
}
public int distanceTo(String v)
{
if (!dist.contains(v)) return Integer.max_value;
return dist.get(v);
}
public Iterable pathTo(String v)
{
Stack path = new Stack();
while (v != null && dist.contains(v))
{
path.push(v);
v = prev.get(v);
}
return path;
}
public static void
main(String[] args)
{
String filename = args[0];
String delimiter = args[1];
In in = new In(filename);
Graph G = GraphGenerator.read(in, delimiter);
String s = args[2];
PathFinder pf = new PathFinder(G, s);
while (!StdIn.isEmpty())
{
String t = StdIn.readLine();
for (String v : pf.pathTo(t))
{
StdOut.println(" " +
v);
}
StdOut.println("distance " + pf.distanceTo(t));
}
}
}
No comments:
Post a Comment