Java Reference
In-Depth Information
The interface in Listing 28-3 combines
BasicGraphInterface
and
GraphAlgorithmsInterface.
LISTING 28-3
An interface for the ADT graph
package
GraphPackage;
public interface
GraphInterface<T>
extends
BasicGraphInterface<T>,
GraphAlgorithmsInterface<T>
{
}
// end GraphInterface
28.28
Example.
Imagine that we want to find the shortest route between the towns of Truro and
Falmouth. By “shortest route” we mean the route with the least number of miles, not the path
with the fewest edges. We first could create the graph in Figure 28-3, using statements much
like those in Segment 28.26. We then could use the method
getCheapestPath
to answer our
question. The following statements indicate how to perform these steps and to display the
names of the cities along the shortest route:
GraphInterface<String> roadMap =
new
UndirectedGraph<String>();
roadMap.addVertex("Provincetown");
roadMap.addVertex("Truro");
. . .
roadMap.addVertex("Falmouth");
roadMap.addEdge("Provincetown", "Truro", 10);
. . .
roadMap.addEdge("Hyannis", "Falmouth", 20);
StackInterface<String> bestRoute =
new
LinkedStack<String>();
double
distance = roadMap.getCheapestPath("Truro", "Falmouth", bestRoute);
System.out.println("The shortest route from Truro to Falmouth is " +
distance + " miles long and " +
"passes through the following towns:");
while
(!bestRoute.isEmpty())
System.out.println(bestRoute.pop());
Note:
The operations of the ADT graph enable you to create a graph and answer questions
about the relationships among its vertices.
Question 13
The previous example finds the shortest route between two towns. Why did
we invoke the method
getCheapestPath
instead of
getShortestPath
?
C
HAPTER
S
UMMARY
A graph is a collection of distinct vertices and distinct edges. Each edge joins two vertices. A subgraph is a
portion of a graph that is itself a graph.
●
A tree is a special graph that has a hierarchical order and a root that is the ancestor of all other nodes—that
is, vertices—in the tree.
●
