University of Phoenix - DAT/305 - Individual: GraphsResource: Ch. 10, "Graphs", of Data Structures: Abstraction and Design Using Java, Exercises for Section 10.4; Self-Check #1Complete the Self-Check
Chapter 10
Graphs
Chapter Objectives
To become familiar with graph terminology and the different types of graphs
To study a Graph ADT (abstract data type) and different implementations of the Graph ADT
To learn the breadth-first and depth-first search traversal algorithms
To learn some algorithms involving weighted graphs
To study some applications of graphs and graph algorithms
One of the limitations of trees is that they cannot represent information structures in which a data item has more than one parent. In this chapter, we introduce a data structure known as a graph that will allow us to overcome this limitation.
Graphs and graph algorithms were being studied long before computers were invented. The advent of the computer made the application of graph algorithms to real-world problems possible. Graphs are especially useful in analyzing networks. Thus, it is not surprising that much of modern graph theory and application was developed at Bell Laboratories, which needed to analyze the very large communications network that is the telephone system. Graph algorithms are also incorporated into the software that makes the Internet function. You can also use graphs to describe a road map, airline routes, or course prerequisites. Computer chip designers use graph algorithms to determine the optimal placement of components on a silicon chip.
You will learn how to represent a graph, determine the shortest path through a graph, and find the minimum subset of a graph.
Graphs
10.1 Graph Terminology
10.2 The Graph ADT and Edge Class
10.3 Implementing the Graph ADT
10.4 Traversals of Graphs
10.5 Applications of Graph Traversals
Case Study: Shortest Path through a Maze
Case Study: Topological Sort of a Graph
10.6Algorithms Using Weighted Graphs
10.1 Graph Terminology
A graph is a data structure that consists of a set of vertices (or nodes) and a set of edges (relations) between the pairs of vertices. The edges represent paths or connections between the vertices. Both the set of vertices and the set of edges must be finite, and either set may be empty. If the set of vertices is empty, naturally the set of edges must also be empty. We restrict our discussion to simple graphs in which there is at most one edge from a given vertex to another vertex.
EXAMPLE 10.1
The following set of vertices, V, and set of edges, E, define a graph that has five vertices, with labels A through E, and four edges.
V = {A, B, C, D, E}
E = {{A, B}, {A, D}, {C, E}, {D, E}}
Each edge is a set of two vertices. There is an edge between A and B (the edge {A, B}), between A and D, between C and E, and between D and E. If there is an edge between any pair of vertices x, y, this means there is a path from vertex x to vertex y and vice versa. We discuss the significance of this shortly.
Visual Representation of Graphs
Visually we represent vertices as points or labeled circles and the edges as lines joining the vertices. Figure 10.1 shows the graph from Example 10.1.
image
FIGURE 10.1 Graph Given in Example 10.1
There are many ways to draw any given graph. The physical layout of the vertices, and even their labeling, are not relevant. Figure 10.2 shows two ways to draw the same graph.
image
FIGURE 10.2 Two Representations of the Same Graph
Directed and Undirected Graphs
The edges of a graph are directed if the existence of an edge from A to B does not necessarily guarantee that there is a path in both directions. A graph that contains directed edges is known as a directed graph or digraph, and a graph that contains undirected edges is known as an undirected graph or simply a graph. A directed edge is like a one-way street; you can travel on it in only one direction. Directed edges are represented as lines with an arrow on one end, whereas undirected edges are represented as single lines. The graph in Figure 10.1 is undirected; Figure 10.3 shows a directed graph. The set of edges for the directed graph follows:
image
FIGURE 10.3 Example of a Directed Graph
E = {(A, B), (B, A), (B, E), (D, A), (E, A), (E, C), (E, D)}
Each edge above is an ordered pair of vertices instead of a set as in an undirected graph. The edge (A, B) means there is a path from A to B. Observe that there is a path from both A to B and from B to A, but these are the only two vertices in which there is an edge in both directions. Our convention will be to denote an edge for a directed graph as an ordered pair (u, v) where this notation means that v (the destination) is adjacent to u (the source). We denote an edge in an undirected graph as the set {u, v}, which means that u is adjacent to v and v is adjacent to u. Therefore, you can create a directed graph that is equivalent to an undirected graph by substituting for each edge {u, v} the ordered pairs (u, v) and (v, u). In general, when we describe graph algorithms in this chapter, we will use the ordered pair notation (u, v) for an edge.
The edges in a graph may have values associated with them known as their weights. A graph with weighted edges is known as a weighted graph. In an illustration of a weighted graph, the weights are shown next to the edges. Figure 10.4 shows an example of a weighted graph. Each weight is the distance between the two cities (vertices) connected by the edge. Generally, the weights are nonnegative, but there are graph problems and graph algorithms that deal with negative weighted edges.
image
FIGURE 10.4 Example of a Weighted Graph
Paths and Cycles
One reason we study graphs is to find pathways between vertices. We use the following definitions to describe pathways between vertices.
A vertex is adjacent to another vertex if there is an edge to it from that other vertex. In Figure 10.4, Philadelphia is adjacent to Pittsburgh. In Figure 10.3, A is adjacent to D, but since this is a directed graph, D is not adjacent to A.
A path is a sequence of vertices in which each successive vertex is adjacent to its predecessor. In Figure 10.5, the following sequence of vertices is a path: Philadelphia → Pittsburgh → Columbus → Indianapolis → Chicago.
In a simple path, the vertices and edges are distinct, except that the first and last vertices may be the same. In Figure 10.5, the path Philadelphia → Pittsburgh → Columbus → Indianapolis → Chicago is a simple path. The path Philadelphia → Pittsburgh → Columbus → Indianapolis → Chicago → Fort Wayne → Indianapolis is a path but not a simple path (see Figure 10.6).
A cycle is a simple path in which only the first and final vertices are the same. In Figure 10.7, the path Pittsburgh → Columbus → Toledo → Cleveland → Pittsburgh is a cycle. For an undirected graph, a cycle must contain at least three distinct vertices. Thus, Pittsburgh → Columbus → Pittsburgh is not considered a cycle.
An undirected graph is called a connected graph if there is a path from every vertex to every other vertex. Figure 10.7 is a connected graph, whereas Figure 10.8 is not.
If a graph is not connected, it is considered unconnected, but it will still consist of connected components. A connected component is a subset of the vertices and the edges connected to those vertices in which there is a path between every pair of vertices in the component. A single vertex with no edges is also considered a connected component. Figure 10.8 consists of the connected components {0, 1, 2, 3, 4, 5, 6}, {7, 8}, and {9, 10, 11, 12}.
image
FIGURE 10.5 A Simple Path
image
FIGURE 10.6 Not a Simple Path
image
FIGURE 10.7 A Cycle
image
FIGURE 10.8 Example of an Unconnected Graph
Relationship between Graphs and Trees
The graph is the most general of the data structures we have studied. It allows for any conceivable relationship among the data elements (the vertices). A tree is actually a special case of a graph. Any graph that is connected and contains no cycles can be viewed as a tree by picking one of its vertices (nodes) as the root. For example, the graph shown in Figure 10.1 can be viewed as a tree if we consider the node labeled D to be the root (see Figure 10.9).
image
FIGURE 10.9 A Graph Viewed as a Tree
Graph Applications
We can use graphs to help solve a number of different kinds of problems. For example, we might want to know whether there is a connection from one node in a network to all others. If we can show that the graph is connected, then a path must exist from one node to every other node.
In college you must take some courses before you take others. These are called prerequisites. Some courses have multiple prerequisites, and some prerequisites have prerequisites of their own. It can be quite confusing. You may even feel that there is a loop in the maze of prerequisites and that it is impossible to schedule your classes to meet the prerequisites. We can represent the set of prerequisites by a directed graph. If the graph has no cycles, then we can find a solution. We can also find the cycles.
Another application would be finding the least-cost path or shortest path from each vertex to all other vertices in a weighted graph. For example, in Figure 10.4, we might want to find the shortest path from Philadelphia to Chicago. Or we might want to create a table showing the distance (miles in the shortest route) between each pair of cities.
EXERCISES FOR SECTION 10.1
SELF-CHECK
In the graph shown in Figure 10.1, what vertices are adjacent to D? Also check in Figure 10.3.
In Figure 10.3, is it possible to get from A to all other vertices? How about from C?
In Figure 10.4, what is the shortest path from Philadelphia to Chicago?
10.2 The Graph ADT and Edge Class
Java does not provide a Graph ADT, so we have the freedom to design our own. To write programs for the applications mentioned at the end of the previous section, we need to be able to navigate through a graph or traverse it (visit all its vertices). To accomplish this, we need to be able to advance from one vertex in a graph to all its adjacent vertices. Therefore, we need to be able to do the following:
Create a graph with the specified number of vertices.
Iterate through all of the vertices in the graph.
Iterate through the vertices that are adjacent to a specified vertex.
Determine whether an edge exists between two vertices.
Determine the weight of an edge between two vertices.
Insert an edge into the graph.
With the exception of item 1, we can specify these requirements in a Java interface. Since a Java interface cannot include a constructor, the requirements for item 1 can only be specified in the comment at the beginning of the interface.
Listing 10.1 gives the declaration of the Graph interface.
LISTING 10.1
Graph.java
import java.util.*;
/** Interface to specify a Graph ADT. A graph is a set of vertices and
a set of edges. Vertices are represented by integers
from 0 to n - 1. Edges are ordered pairs of vertices.
Each implementation of the Graph interface should
provide a constructor that specifies the number of
vertices and whether or not the graph is directed.
*/
public interface Graph {
// Accessor Methods
/** Return the number of vertices.
@return The number of vertices
*/
int getNumV();
/** Determine whether this is a directed graph.
@return true if this is a directed graph
*/
boolean isDirected();
/** Insert a new edge into the graph.
@param edge The new edge
*/
void insert(Edge edge);
/** Determine whether an edge exists.
@param source The source vertex
@param dest The destination vertex
@return true if there is an edge from source to dest
*/
boolean isEdge(int source, int dest);
/** Get the edge between two vertices.
@param source The source vertex
@param dest The destination vertex
@return The Edge between these two vertices
or null if there is no edge
*/
Edge getEdge(int source, int dest);
/** Return an iterator to the edges connected to a given vertex.
@param source The source vertex
@return An Iterator<Edge> to the vertices connected to source
*/
Iterator<Edge> edgeIterator(int source);
Representing Vertices and Edges
Before we can implement this interface, we must decide how to represent the vertices and edges of a graph. We can represent the vertices by integers from 0 up to, but not including, |V|. (|V| means the cardinality of V, or the number of vertices in set V.) For edges we will define the class Edge that will contain the source vertex, the destination vertex, and the weight. For unweighted edges we will use the default value of 1.0. Table 10.1 shows the Edge class. Observe that an Edge is directed. For undirected graphs, we will always have two Edge objects: one in each direction for each pair of vertices that has an edge between them. A vertex is represented by a type int variable.
TABLE 10.1 The Edge Class
Data Field Attribute
private int dest The destination vertex for an edge
private int source The source vertex for an edge
private double weight The weight
Constructor Purpose
public Edge(int source, int dest) Constructs an Edge from source to dest. Sets the weight to 1.0
public Edge(int source, int dest, double w) Constructs an Edge from source to dest. Sets the weight to w
Method Behavior
public boolean equals(Object o) Compares two edges for equality. Edges are equal if their source and destination vertices are the same. The weight is not considered
public int getDest() Returns the destination vertex
public int getSource() Returns the source vertex
public double getWeight() Returns the weight
public int hashCode() Returns the hash code for an edge. The hash code depends only on the source and destination
public String toString() Returns a string representation of the edge
EXERCISES FOR SECTION 10.2
SELF-CHECK
Use the constructors in Table 10.1 to create the Edge objects connecting vertices 9 through 12 for the graph in Figure 10.8.
PROGRAMMING
Implement the Edge class.
10.3 Implementing the Graph ADT
Because graph algorithms have been studied and implemented throughout the history of computer science, many of the original publications of graph algorithms and their implementations did not use an object-oriented approach and did not even use ADTs. The implementation of the graph was done in terms of fundamental data structures that were used directly in the algorithm. Different algorithms would use different representations.
Two representations of graphs are most common:
Edges are represented by an array of lists called adjacency lists, where each list stores the vertices adjacent to a particular vertex.
Edges are represented by a two-dimensional array, called an adjacency matrix, with |V| rows and |V| columns.
Adjacency List
An adjacency list representation of a graph uses an array of lists. There is one list for each vertex. Figure 10.10 shows an adjacency list representation of a directed graph. The list referenced by array element 0 shows the vertices (1 and 3) that are adjacent to vertex 0. The vertices are in no particular order. For simplicity, we are showing just the destination vertex as the value field in each node of the adjacency list, but in the actual implementation the entire Edge will be stored. Instead of storing value = 1 (the destination vertex) in the first vertex adjacent to 0, we will store a reference to the Edge (0, 1, 1.0) where 0 is the source, 1 is the destination, and 1.0 is the weight. The Edge must be stored (not just the destination) because weighted graphs can have different values for weights.
image
FIGURE 10.10 Adjacency List Representation of a Directed Graph
For an undirected graph (or simply a “graph”), symmetric entries are required. Thus, if {u, v} is an edge, then v will appear on the adjacency list for u and u will appear on the adjacency list for v. Figure 10.11 shows the adjacency list representation for an undirected graph. The actual lists will store references to Edges.
image
FIGURE 10.11 Adjacency List Representation of an Undirected Graph
Adjacency Matrix
The adjacency matrix uses a two-dimensional array to represent the graph. For an unweighted graph, the entries in this matrix can be boolean values, where true represents the presence of an edge and false its absence. Another popular method is to use the value 1 for an edge and 0 for no edge. The integer coding has benefits over the boolean approach for some graph algorithms that use matrix multiplication.
For a weighted graph, the matrix would contain the weights. Since 0 is a valid weight, we will use Double.POSITIVE_INFINITY (a special double value in Java that approximates the mathematical behavior of infinity) to indicate the absence of an edge, and in an unweighted graph we will use a weight of 1.0 to indicate the presence of an edge.
Figure 10.12 shows a directed graph and the corresponding adjacency matrix. Instead of using Edge objects, an edge is indicated by the value 1.0, and the lack of an edge is indicated by a blank space.
image
FIGURE 10.12 Directed Graph and Corresponding Adjacency Matrix
If the graph is undirected, then the matrix is symmetric, and only the lower diagonal of the matrix needs be saved (the colored squares in Figure 10.13).
image
FIGURE 10.13 Undirected Graph and Adjacency Matrix Representation
Overview of the Hierarchy
We will describe Java classes that use each representation. Each class will extend a common abstract superclass. The interface Graph was introduced in Section 10.2. The class Edge was also described in that section.
We will define the class AbstractGraph to represent a graph in general. The classes ListGraph and MatrixGraph will provide concrete representations of graphs using an adjacency list and adjacency matrix, respectively (see Figure 10.14). The MatrixGraph class contains an inner class (indicated by the ⊕ symbol) that we call Iter, which implements the Iterator<Edge> interface.
image
FIGURE 10.14 UML Class Diagram of Graph Class Hierarchy
Class AbstractGraph
We will use an abstract class, AbstractGraph, as the common superclass for graph implementations. This will enable us to implement some of the methods for the Graph interface in the abstract superclass and leave other methods that are implementation specific to its subclasses. Graph algorithms will be designed to work on objects that meet the requirements defined by this abstract class. This class is summarized in Table 10.2. Note that the methods edgeIterator, getEdge, insert, and isEdge, which are required by the Graph interface (see Listing 10.1), are implicitly declared abstract and must be declared in the concrete subclasses.
TABLE 10.2 The Abstract Class AbstractGraph
Data Field Attribute
private boolean directed true if this is a directed graph
private int numV The number of vertices
Constructor Purpose
public AbstractGraph(int numV, boolean directed) Constructs an empty graph with the specified number of vertices and with the specified directed flag. If directed is true, this is a directed graph
Method Behavior
public int getNumV() Gets the number of vertices
public boolean isDirected() Returns true if the graph is a directed graph
public void loadEdgesFromFile(Scanner scan) Loads edges from a data file
public static Graph createGraph (Scanner scan, boolean isDirected, String type) Factory method to create a graph and load the data from an input file
Implementation
The implementation is shown in Listing 10.2. Method loadEdgesFromFile reads edges from individual lines of a data file (see Programming Exercise 1).
LISTING 10.2
AbstractGraph.java
import java.util.*;
import java.io.*;
/** Abstract base class for graphs. A graph is a set of vertices and
a set of edges. Vertices are represented by integers
from 0 to n - 1. Edges are ordered pairs of vertices.
*/
public abstract class AbstractGraph implements Graph {
// Data Fields
/** The number of vertices */
private int numV;
/** Flag to indicate whether this is a directed graph */
private boolean directed;
// Constructor
/** Construct a graph with the specified number of vertices and the directed
flag. If the directed flag is true, this is a directed graph.
@param numV The number of vertices
@param directed The directed flag
*/
public AbstractGraph(int numV, boolean directed) {
this.numV = numV;
this.directed = directed;
}
// Accessor Methods
/** Return the number of vertices.
@return The number of vertices
*/
public int getNumV() {
return numV;
}
/** Return whether this is a directed graph.
@return true if this is a directed graph
*/
public boolean isDirected() {
return directed;
}
// Other Methods
/** Load the edges of a graph from the data in an input file. The file
should contain a series of lines, each line with two or
three data values. The first is the source, the second is
the destination, and the optional third is the weight.
@param scan The Scanner connected to the data file
*/
public void loadEdgesFromFile(Scanner scan) {
// Programming Exercise 1
}
/** Factory method to create a graph and load the data from an input
file. The first line of the input file should contain the number
of vertices. The remaining lines should contain the edge data as
described under loadEdgesFromFile.
@param scan The Scanner connected to the data file
@param isDirected true if this is a directed graph,
false otherwise
@param type The string "Matrix" if an adjacency matrix is to be
created, and the string "List" if an adjacency list
is to be created
@throws IllegalArgumentException if type is neither "Matrix"
nor "List"
*/
public static Graph createGraph(Scanner scan, boolean isDirected,
String type) {
int numV = scan.nextInt();
AbstractGraph returnValue; type = type.toLowerCase();
switch (type) {
case "matrix":
returnValue = new MatrixGraph(numV, isDirected);
break;
case "list":
returnValue = new ListGraph(numV, isDirected);
break;
default:
throw new IllegalArgumentException();
}
returnValue.loadEdgesFromFile(scan);
return returnValue;
}
The ListGraph Class
The ListGraph class extends the AbstractGraph class by providing an internal representation using an array of lists. Table 10.3 describes the ListGraph class.
TABLE 10.3 The ListGraph Class
Data Field Attribute
private List<Edge>[] edges An array of Lists to contain the edges that originate with each vertex
Constructor Purpose
public ListGraph(int numV, boolean directed) Constructs a graph with the specified number of vertices and directionality
Method Behavior
public Iterator<Edge> edgeIterator(int source) Returns an iterator to the edges that originate from a given vertex
public Edge getEdge(int source, int dest) Gets the edge between two vertices
public void insert(Edge e) Inserts a new edge into the graph
public boolean isEdge(int source, int dest) Determines whether an edge exists from vertex source to dest
The Data Fields
The class begins as follows:
import java.util.*;
/** A ListGraph is an extension of the AbstractGraph abstract class
that uses an array of lists to represent the edges.
*/
public class ListGraph extends AbstractGraph {
// Data Field
/** An array of Lists to contain the edges that
originate with each vertex. */
private List<Edge>[] edges;
. . .
The Constructor
The constructor allocates an array of LinkedLists, one for each vertex.
/** Construct a graph with the specified number of vertices and directionality.
@param numV The number of vertices
@param directed The directionality flag
*/
public ListGraph(int numV, boolean directed) {
super(numV, directed);
edges = new List[numV];
for (int i = 0; i < numV; i++) {
edges[i] = new LinkedList<Edge>();
}
}
The isEdge Method
Method isEdge determines whether an edge exists by searching the list associated with the source vertex for an entry. This is done by calling the contains method for the List.
/** Determine whether an edge exists.
@param source The source vertex
@param dest The destination vertex
@return true if there is an edge from source to dest
*/
public boolean isEdge(int source, int dest) {
return edges[source].contains(new Edge(source, dest));
}
Observe that we had to create a dummy Edge object for the contains method to search for. The Edge.equals method does not check the edge weights, so the weight parameter is not needed.
The insert Method
The insert method inserts a new edge (source, destination, weight) into the graph by adding that edge's data to the list of adjacent vertices for that edge's source. If the graph is not directed, it adds a new edge in the opposite direction (destination, source, weight) to the list of adjacent vertices for that edge's destination.
/** Insert a new edge into the graph.
@param edge The new edge
*/
public void insert(Edge edge) {
edges[edge.getSource()].add(edge);
if (!isDirected()) {
edges[edge.getDest()].add(new Edge(edge.getDest(), edge.getSource(),
edge.getWeight()));
}
}
The edgeIterator Method
The edgeIterator method will return an Iterator<Edge> object that can be used to iterate through the edges adjacent to a given vertex. Because each LinkedList entry in the array edges is a List<Edge>, its iterator method will provide the desired object. Thus, the edgeIterator merely calls the corresponding iterator method for the specified vertex.
public Iterator<Edge> edgeIterator(int source) {
return edges[source].iterator();
}
The getEdge Method
Similar to the isEdge method, the getEdge method also requires a search. However, we need to program the search directly. We will use the enhanced for statement to access all edges in the list for vertex source. We compare each edge to a target object with source and destination set to the method arguments. The equals method does not compare edge weights, only the vertices.
/** Get the edge between two vertices.
@param source The source
@param dest The destination
@return the edge between these two vertices
or null if an edge does not exist.
*/
public Edge getEdge(int source, int dest) {
Edge target = new Edge(source, dest, Double.POSITIVE_INFINITY);
for (Edge edge: edges[source]) {
if (edge.equals(target))
return edge; // Desired edge found, return it.
}
// Assert: All edges for source checked.
return null; // Desired edge not found.
}
The MatrixGraph Class
The MatrixGraph class extends the AbstractGraph class by providing an internal representation using a two-dimensional array for storing the edge weights
double[][] edges;
When a new MatrixGraph object is created, the constructor sets the number of rows (vertices) in this array. It implements the same methods as class ListGraph and also has an inner iterator class Iter. It needs its own iterator class because there is no Iterator class associated with an array. The implementation is left as a project (Programming Project 1).
Comparing Implementations
Time Efficiency
The two implementations present a tradeoff. Which is best depends on the algorithm and the density of the graph. The density of a graph is the ratio of |E| to |V|2. A dense graph is one in which |E| is close to but less than |V|2, and a sparse graph is one in which |E| is much less than |V|2. Therefore, for a dense graph we can assume that |E| is O(|V|2), and for a sparse graph we can assume that |E| is O(|V|).
Many graph algorithms are of the form:
1. for each vertex u in the graph
2. for each vertex v adjacent to u
3. Do something with edge (u, v).
For an adjacency list representation, Step 1 is O(|V|) and Step 2 is O(|Eu|), where |Eu| is the number of edges that originate at vertex u. Thus, the combination of Steps 1 and 2 will represent examining each edge in the graph, giving O(|E|). For an adjacency matrix representation, Step 2 is also O(|V|), and thus the overall algorithm is O(|V|2). Thus, for a sparse graph, the adjacency list gives better performance for this type of algorithm, whereas for a dense graph, the performance is the same for either representation.
Some graph algorithms are of the form
1. for each vertex u in some subset of the vertices
2. for each vertex v in some subset of the vertices
3. if (u, v) is an edge
4. Do something with edge (u, v).
For an adjacency matrix representation, Step 3 tests a matrix value and is O(1), so the overall algorithm is O(|V|2). However, for an adjacency list representation, Step 3 searches a list and is O(|Eu|), so the combination of Steps 2 and 3 is O(|E|) and the overall algorithm is O(|V||E|). For a dense graph, the adjacency matrix gives the best performance for this type of algorithm, and for a sparse graph, the performance is the same for both representations.
Thus, if a graph is dense, the adjacency matrix representation is best, and if a graph is sparse, the adjacency list representation is best. Intuitively, this makes sense because a sparse graph will lead to a sparse matrix, or one in which most entries are POSITIVE_INFINITY. These entries are not included in a list representation, so they will have no effect on processing time. However, they are included in a matrix representation and will have an undesirable impact on processing time.
Storage Efficiency
Note that storage is allocated for all vertex combinations (or at least half of them) in an adjacency matrix. So the storage required is proportional to |V|2. If the graph is sparse (not many edges), there will be a lot of wasted space in the adjacency matrix. In an adjacency list, only the adjacent edges are stored.
On the other hand, in an adjacency list, each edge is represented by a reference to an Edge object containing data about the source, destination, and weight. There is also a reference to the next edge in the list. In a matrix representation, only the weight associated with an edge is stored. So each element in an adjacency list requires approximately four times the storage of an element in an adjacency matrix.
Based on this, we can conclude that the break-even point in terms of storage efficiency occurs when approximately 25 percent of the adjacency matrix is filled with meaningful data. That is, the adjacency list uses less (more) storage when less than (more than) 25 percent of the adjacency matrix would be filled.
The MapGraph Class
We can achieve the performance benefits of both the ListGraph and MatrixGraph by making a slight modification to the ListGraph. Replacing the array of List<Edge> with an array of Map<Integer, Edge> allows us to query the existence of an edge in O(1) time, and using the LinkedHashMap allows iterating through the edges adjacent to a given vertex in O(|Eu|). The constructor is changed to
public MapGraph(int numV, boolean isDirected) {
super(numV, isDirected);
outgoingEdges = new Map[numV];
for (int i = 0; i < numV; i++) {
outgoingEdges[i] = new LinkedHashMap<>();
}
}
The insertEdge method is changed to
public void insertEdge(Edge edge) {
int source = edge.getSource();
int dest = edge.getDest();
double weight = edge.getWeight();
outgoingEdges[source].put(dest, edge);
if (!isDirected()) {
Edge reverseEdge = new Edge(dest, source, weight);
outgoingEdges[dest].put(source, reverseEdge);
}
}
The isEdge and getEdge methods are simplified to
public boolean isEdge(int source, int dest) {
return outgoingEdges[source].containsKey(dest);
}
public Edge getEdge(int source, int dest) {
return outgoingEdges[source].get(dest);
}
And the edgeIterator becomes
public Iterator<Edge> edgeIterator(int source) {
return outgoingEdges[source].values().iterator();
}
EXERCISES FOR SECTION 10.3
SELF-CHECK
Represent the following graphs using adjacency lists.
image
Represent the graphs in Exercise 1 above using an adjacency matrix.
For each graph in Exercise 1, what are the |V|, the |E|, and the density? Which representation is best for each graph? Explain your answers.
PROGRAMMING
Implement the loadEdgesFromFile method for class AbstractGraph. If there are two values on a line, an edge with the default weight of 1.0 is inserted; if there are three values, the third value is the weight.
10.4 Traversals of Graphs
Most graph algorithms involve visiting each vertex in a systematic order. Just as with trees, there are different ways to do this. The two most common traversal algorithms are breadth first and depth first. Although these are graph traversals, they are more commonly called breadth-first and depth-first search.
Breadth-First Search
In a breadth-first search, we visit the start node first, then all nodes that are adjacent to it next, then all nodes that can be reached by a path from the start node containing two edges, three edges, and so on. The requirement for a breadth-first search is that we must visit all nodes for which the shortest path from the start node is length k before we visit any node for which the shortest path from the start node is length k + 1. You can visualize a breadth-first traversal by “picking up” the graph at the vertex that is the start node, so the start node will be the highest node and the rest of the nodes will be suspended underneath it, connected by their edges. In a breadth-first search, the nodes that are higher up in the picked-up graph are visited before nodes that are lower in the graph.
Breadth-first search starts at some vertex. Unlike the case of a tree, there is no special start vertex, so we will arbitrarily pick the vertex with label 0. We then visit it by identifying all vertices that are adjacent to the start vertex. Then we visit each of these vertices, identifying all of the vertices adjacent to them. This process continues until all vertices are visited. If the graph is not a connected graph, then the process is repeated with one of the unidentified vertices. In the discussion that follows, we use color to distinguish among three states for a node: identified (light gray), visited (dark gray), and not identified (white). Initially, all nodes are not identified. If a node is in the identified state, that node was encountered while visiting another, but it has not yet been visited.
Example of Breadth-First Search
Consider the graph shown in Figure 10.15. We start at vertex 0 and color it light gray (see Figure 10.16(a)). We visit 0 and see that 1 and 3 are adjacent, so we color them light gray (to show that they have been identified). We are finished visiting 0 and now color it dark gray (see Figure 10.16(b)). So far we have visited node 0.
image
FIGURE 10.15 Graph to Be Traversed Breadth First
image
FIGURE 10.16 Example of a Breadth-First Search
We always select the first node that was identified (light gray) but not yet visited and visit it next. Therefore, we visit 1 and look at its adjacent vertices: 0, 2, 4, 6, and 7. We skip 0 because it is not colored white, and we color the others light gray. Then we color 1 dark gray (see Figure 10.16(c)). Now we have visited nodes 0 and 1.
Then we look at 3 (the first of the light gray vertices in Figure 10.16(c) to have been identified) and see that its adjacent vertex, 2, has already been identified and 0 has been visited, so we are finished with 3 (see Figure 10.16(d)). Now we have visited nodes 0, 1, and 3, which are the starting vertex and all vertices adjacent to it.
Now we visit 2 and see that 8 and 9 are adjacent. Then we visit 4 and see that 5 is the only adjacent vertex not identified or visited (Figure 10.16(e)). Finally, we visit 6 and 7 (the last vertices that are two edges away from the starting vertex), then 8, 9, and 5, and see that there are no unidentified vertices (Figure 10.16(f)). The vertices have been visited in the sequence 0, 1, 3, 2, 4, 6, 7, 8, 9, 5.
Algorithm for Breadth-First Search
To implement breadth-first search, we need to be able to determine the first identified vertex that has not been visited so that we can visit it. To ensure that the identified vertices are visited in the correct sequence, we will store them in a queue (first-in, first-out). When we need a new node to visit, we remove it from the queue. We summarize the process in the following algorithm.
Algorithm for Breadth-First Search
1. Take an arbitrary start vertex, mark it identified (color it light gray), and place it in a queue.
2. while the queue is not empty
3. Take a vertex, u, out of the queue and visit u.
4. for all vertices, v, adjacent to this vertex, u
5. if v has not been identified or visited
6. Mark it identified (color it light gray).
7. Insert vertex v into the queue.
8. We are now finished visiting u (color it dark gray).
Table 10.4 traces this algorithm on the graph shown earlier in Figure 10.15. The initial queue contents is the start node, 0. The first line shows that after we finish visiting vertex 0, the queue contains nodes 1 and 3, which are adjacent to node 0 and are colored light gray in Figure 10.16(b). The second line shows that after removing 1 from the queue and visiting 1, we insert its neighbors that have not yet been identified or visited: nodes 2, 4, 6, and 7.
TABLE 10.4 Trace of Breadth-First Search of Graph in Figure 10.15
Vertex Being Visited Queue Contents after Visit Visit Sequence
0 1 3 0
1 3 2 4 6 7 0 1
3 2 4 6 7 0 1 3
2 4 6 7 8 9 0 1 3 2
4 6 7 8 9 5 0 1 3 2 4
6 7 8 9 5 0 1 3 2 4 6
7 8 9 5 0 1 3 2 4 6 7
8 9 5 0 1 3 2 4 6 7 8
9 5 0 1 3 2 4 6 7 8 9
5 Empty 0 1 3 2 4 6 7 8 9 5
Table 10.4 shows that the nodes were visited in the sequence 0, 1, 3, 2, 4, 6, 7, 8, 9, 5. There are other sequences that would also be valid breadth-first traversals.
We can also build a tree that represents the order in which vertices would be visited in a breadth-first traversal, by attaching the vertices as they are identified to the vertex from which they are identified. Such a tree is shown in Figure 10.17. Observe that this tree contains all of the vertices and some of the edges of the original graph. A path starting at the root to any vertex in the tree is the shortest path in the original graph from the start vertex to that vertex, where we consider all edges to have the same weight. Therefore, the shortest path is the one that goes through the smallest number of vertices. We can save the information we need to represent this tree by storing the parent of each vertex when we identify it (Step 7 of the breadth-first algorithm).
image
FIGURE 10.17 Breadth-First Search Tree of Graph in Figure 10.15
Refinement of Step 7 of Breadth-First Search Algorithm
7.1 Insert vertex v into the queue.
7.2 Set the parent of v to u.
Performance Analysis of Breadth-First Search
The loop at Step 2 will be performed for each vertex. The inner loop at Step 4 is performed for |Ev| (the number of edges that originate at that vertex). The total number of steps is the sum of the edges that originate at each vertex, which is the total number of edges. Thus, the algorithm is O(|E|).
Implementing Breadth-First Search
Listing 10.3 shows method breadthFirstSearch. Note that nothing is done when we have finished visiting a vertex (algorithm Step 8).
This method declares three data structures: int[] parent, boolean[] identified, and Queue theQueue. The array identified is used to keep track of the nodes that have been previously encountered, and theQueue is used to store nodes that are waiting to be visited.
The method returns array parent, which could be used to construct the breadth-first search tree. The element parent[v] contains the parent of vertex v in the tree. The statement
parent[neighbor] = current;
is used to “insert an edge into the breadth-first search tree.” It does this by setting the parent of a newly identified node (neighbor) as the node being visited (current). If we run the breadthFirstSearch method on the graph shown in Figure 10.15, then the array parent will be defined as follows:
image
If you compare array parent to Figure 10.17, you can see that parent[i] is the parent of vertex i. For example, the parent of vertex 4 is vertex 1. The entry parent[0] is –1 because node 0 is the start vertex.
Although array parent could be used to construct the breadth-first search tree, we are generally not interested in the complete tree but rather in the path from the root to a given vertex. Using array parent to trace the path from that vertex back to the root would give you the reverse of the desired path. For example, the path derived from parent for vertex 4 to the root would be 4 to 1 to 0. If you place these vertices in a stack and then pop the stack until it is empty, you will get the path from the root: 0 to 1 to 4.
LISTING 10.3
Class BreadthFirstSearch.java
/** Class to implement the breadth-first search algorithm. */
public class BreadthFirstSearch {
/** Perform a breadth-first search of a graph.
@post The array parent will contain the predecessor
of each vertex in the breadth-first search tree.
@param graph The graph to be searched
@param start The start vertex
@return The array of parents
*/
public static int[] breadthFirstSearch(Graph graph, int start) {
Queue<Integer> theQueue = new LinkedList<Integer>();
// Declare array parent and initialize its elements to –1.
int[] parent = new int[graph.getNumV()];
for (int i = 0; i < graph.getNumV(); i++) {
parent[i] = -1;
}
// Declare array identified and
// initialize its elements to false.
boolean[] identified = new boolean[graph.getNumV()];
/* Mark the start vertex as identified and insert it into the queue */
identified[start] = true;
theQueue.offer(start);
/* Perform breadth-first search until done */
while (!theQueue.isEmpty()) {
/* Take a vertex, current, out of the queue. (Begin visiting current). */
int current = theQueue.remove();
/* Examine each vertex, neighbor, adjacent to current. */
Iterator<Edge> itr = graph.edgeIterator(current);
while (itr.hasNext()) {
Edge edge = itr.next();
int neighbor = edge.getDest();
// If neighbor has not been identified
if (!identified[neighbor]) {
// Mark it identified.
identified[neighbor] = true;
// Place it into the queue.
theQueue.offer(neighbor);
/* Insert the edge (current, neighbor) into the tree. */
parent[neighbor] = current;
}
}
// Finished visiting current.
}
return parent;
}
Depth-First Search
Another way to traverse a graph is depth-first search. In depth-first search you start at a vertex, visit it, and choose one adjacent vertex to visit. Then choose a vertex adjacent to that vertex to visit, and so on until you go no further. Then back up and see whether a new vertex (one not previously visited) can be found. In the discussion that follows, we use color to distinguish among three states for a node: being visited (light gray), finished visiting (dark gray), and not yet visited (white). Initially, of course, all nodes are not yet visited. Note that the color light gray is used in depth-first search to indicate that a vertex is in the process of being visited, whereas it was used in our discussion of breadth-first search to indicate that the vertex was identified.
Example of Depth-First Search
Consider the graph shown in Figure 10.18. We can start at any vertex, but for simplicity we will start at 0. The vertices adjacent to 0 are 1, 2, 3, and 4. We mark 0 as being visited (color it light gray; see Figure 10.19(a)). Next we consider 1. We mark 1 as being visited (see Figure 10.19(b)). The vertices adjacent to 1 are 0, 3, and 4. But 0 is being visited, so we recursively apply the algorithm with 3 as the start vertex. We mark 3 as being visited (see Figure 10.19(c)). The vertices adjacent to 3 are 0, 1, and 4. Because 0 and 1 are already being visited, we recursively apply the algorithm with 4 as the start vertex. We mark 4 as being visited (see Figure 10.19(d)). The vertices adjacent to 4 are 0, 1, and 3. All of these are being visited, so we mark 4 as finished (see Figure 10.19(e)) and return from the recursion. Now all of the vertices adjacent to 3 have been visited, so we mark 3 as finished and return from the recursion. Now all of the vertices adjacent to 1 have been visited, so we mark 1 as finished and return from the recursion to the original start vertex, 0. The order in which we started to visit vertices is 0, 1, 3, 4; the order in which vertices have become finished so far is 4, 3, 1.
image
FIGURE 10.18 Graph to Be Traversed Depth First
image
FIGURE 10.19 Example of Depth-First Search
We now consider vertex 2, which is adjacent to 0 but has not been visited. We mark 2 as being visited (see Figure 10.19(f)) and consider the vertices adjacent to it: 5 and 6. We mark 5 as being visited (see Figure 10.19(g)) and consider the vertices adjacent to it: 2 and 6. Because 2 is already being visited, we next visit 6. We mark 6 as being visited (see Figure 10.19(h)). The vertices adjacent to 6 (2 and 5) are already being visited. Thus, we mark 6 as finished and recursively return. The vertices adjacent to 5 have all been visited, so we mark 5 as finished and return from the recursion. All of the vertices adjacent to 2 have been visited, so we mark 2 as finished and return from the recursion.
Finally, we come back to 0. Because all of the vertices adjacent to it have also been visited, we mark 0 as finished and we are done (see Figure 10.19(i)). The order in which we started to visit all vertices is 0, 1, 3, 4, 2, 5, 6; the order in which we finished visiting all vertices is 4, 3, 1, 6, 5, 2, 0. The discovery order is the order in which the vertices are discovered. The finish order is the order in which the vertices are finished. We consider a vertex to be finished when we return to it after finishing all its successors.
Figure 10.20 shows the depth-first search tree for the graph in Figure 10.18. A preorder traversal of this tree yields the sequence in which the vertices were visited: 0, 1, 3, 4, 2, 5, 6. The dashed lines are the other edges in the graph that are not part of the depth-first search tree. These edges are called back edges because they connect a vertex with its ancestors in the depth-first search tree. Observe that vertex 4 has two ancestors in addition to its parent 3: 1 and 0. Vertex 1 is a grandparent, and vertex 0 is a great-grandparent.
image
FIGURE 10.20 Depth-First Search Tree of Figure 10.18
Algorithm for Depth-First Search
Depth-first search is used as the basis of other graph algorithms. However, rather than embedding the depth-first search algorithm into these other algorithms, we will implement the depth-first search algorithm to collect information about the vertices, which we can then use in these other algorithms. The information we will collect is the discovery order (or the visit order) and the finish order.
The depth-first search algorithm follows. Step 5 recursively applies this algorithm to each vertex as it is discovered.
Algorithm for Depth-First Search
1. Mark the current vertex, u, visited (color it light gray), and enter it in the discovery order list.
2. for each vertex, v, adjacent to the current vertex, u
3. if v has not been visited
4. Set parent of v to u.
5. Recursively apply this algorithm starting at v.
6. Mark u finished (color it dark gray) and enter u into the finish order list.
Observe that Step 6 is executed after the loop in Step 2 has examined all vertices adjacent to vertex u. Also, the loop at Step 2 does not select the vertices in any particular order.
Table 10.5 shows a trace of the algorithm as applied to the graph shown in Figure 10.19. We list each visit or finish step in column 1. Column 2 lists the vertices adjacent to each vertex when it begins to be visited. The discovery order (the order in which the vertices are visited) is 0, 1, 3, 4, 2, 5, 6. The finish order is 4, 3, 1, 6, 5, 2, and 0.
TABLE 10.5 Trace of Depth-First Search of Figure 10.19
Operation Adjacent Vertices Discovery (Visit) Order Finish Order
Visit 0 1, 2, 3, 4 0
Visit 1 0, 3, 4 0, 1
Visit 3 0, 1, 4 0, 1, 3
Visit 4 0, 1, 3 0, 1, 3, 4
Finish 4 4
Finish 3 4, 3
Finish 1 4, 3, 1
Visit 2 0, 5, 6 0, 1, 3, 4, 2
Visit 5 2, 6 0, 1, 3, 4, 2, 5
Visit 6 2, 5 0, 1, 3, 4, 2, 5, 6
Finish 6 4, 3, 1, 6
Finish 5 4, 3, 1, 6, 5
Finish 2 4, 3, 1, 6, 5, 2
Finish 0 4, 3, 1, 6, 5, 2, 0
Performance Analysis of Depth-First Search
The loop at Step 2 is executed |Eu| (the number of edges that originate at that vertex) times. The recursive call results in this loop being applied to each vertex. The total number of steps is the sum of the edges that originate at each vertex, which is the total number of edges |E|. Thus, the algorithm is O(|E|).
There is an implicit Step 0 to the algorithm that colors all of the vertices white. This is O(|V|); thus, the total running time of the algorithm is O(|V|+|E|).
Implementing Depth-First Search
The class DepthFirstSearch is designed to be used as a building block for other algorithms. When constructed, this class performs a depth-first search on a graph and records the start time, finish time, start order, and finish order. For an unconnected graph or for a directed graph (whether connected or not), a depth-first search may not visit each vertex in the graph. Thus, once the recursive method returns, the vertices need to be examined to see whether they all have been visited; if not, the recursive process repeats, starting with the next unvisited vertex. Thus, the depth-first search can generate more than one tree. We will call this collection of trees a forest. Also, it may be important that we control the order in which the vertices are examined to form the forest. Thus, one of the constructors for the DepthFirstSearch class enables its caller to specify the order in which vertices are examined to select a new start vertex. The default is normal ascending order. The class is described in Table 10.6, and part of the code is shown in Listing 10.4.
TABLE 10.6 Class DepthFirstSearch
Data Field Attribute
private int discoverIndex The index that indicates the discovery order
private int[] discoveryOrder The array that contains the vertices in discovery order
private int finishIndex The index that indicates the finish order
private int[] finishOrder The array that contains the vertices in finish order
private Graph graph A reference to the graph being searched
private int[] parent The array of predecessors in the depth-first search tree
private boolean[] visited An array of boolean values to indicate whether or not a vertex has been visited
Constructor Purpose
public DepthFirstSearch(Graph graph) Constructs the depth-first search of the specified graph selecting the start vertices in ascending vertex order
public DepthFirstSearch(Graph graph, int[] order) Constructs the depth-first search of the specified graph selecting the start vertices in the specified order. The first vertex visited is order[0]
Method Behavior
public void depthFirstSearch(int s) Recursively searches the graph starting at vertex s
public int[] getDiscoveryOrder() Gets the discovery order
public int[] getFinishOrder() Gets the finish order
public int[] getParent() Gets the parents in the depth-first search tree
Each constructor allocates storage for the arrays parent, visited, discoveryOrder, and finishOrder and initializes all elements of parent to -1 (no parent). In the constructor in Listing 10.4, the for statement
for (int i = 0; i < n; i++) {
if (!visited[i])
depthFirstSearch(i);
}
calls the recursive depth-first search method. Method depthFirstSearch follows the algorithm shown earlier. If the graph is connected, all vertices will be visited after the return from the initial call to depthFirstSearch. If the graph is not connected, additional calls will be made using a start vertex that has not been visited.
In the constructor (not shown) that allows the client to control the order of selection for start vertices, the parameter int[] order specifies this sequence. To code this constructor, change the if statement in the for loop of the first constructor to
if (!visited[order[i]])
depthFirstSearch(order[i]);
The rest of the code is the same.
LISTING 10.4
DepthFirstSearch.java
/** Class to implement the depth-first search algorithm. */
public class DepthFirstSearch {
// Data Fields
/** A reference to the graph being searched. */
private Graph graph;
/** Array of parents in the depth-first search tree. */
private int[] parent;
/** Flag to indicate whether this vertex has been visited. */
private boolean[] visited;
/** The array that contains each vertex in discovery order. */
private int[] discoveryOrder;
/** The array that contains each vertex in finish order. */
private int[] finishOrder;
/** The index that indicates the discovery order. */
private int discoverIndex = 0;
/** The index that indicates the finish order. */
private int finishIndex = 0;
// Constructors
/** Construct the depth-first search of a Graph starting at
vertex 0 and visiting the start vertices in ascending order.
@param graph The graph
*/
public DepthFirstSearch(Graph graph) {
this.graph = graph;
int n = graph.getNumV();
parent = new int[n];
visited = new boolean[n];
discoveryOrder = new int[n];
finishOrder = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = -1;
}
for (int i = 0; i < n; i++) {
if (!visited[i])
depthFirstSearch(i);
}
}
/** Construct the depth-first search of a Graph
selecting the start vertices in the specified order.
The first vertex visited is order[0].
@param graph The graph
@param order The array giving the order
in which the start vertices should be selected
*/
public DepthFirstSearch(Graph graph, int[] order) {
// Same as constructor above except for the if statement.
}
/** Recursively depth-first search the graph starting at vertex current.
@param current The start vertex
*/
public void depthFirstSearch(int current) {
/* Mark the current vertex visited. */
visited[current] = true;
discoveryOrder[discoverIndex++] = current;
/* Examine each vertex adjacent to the current vertex */
Iterator<Edge> itr = graph.edgeIterator(current);
while (itr.hasNext()) {
int neighbor = itr.next().getDest();
/* Process a neighbor that has not been visited */
if (!visited[neighbor]) {
/* Insert (current, neighbor) into the depth-first search tree. */
parent[neighbor] = current;
/* Recursively apply the algorithm starting at neighbor. */
depthFirstSearch(neighbor);
}
}
/* Mark current finished. */
finishOrder[finishIndex++] = current;
}
Testing Method depthFirstSearch
Next, we show a main method that tests the class. It is a simple driver program that can be used to read a graph and then initiate a depth-first traversal. After the traversal, the driver program displays the arrays that represent the search results.
/** Main method to test depth-first search method
@pre args[0] is the name of the input file.
@param args The command line arguments
*/
public static void main(String[] args) {
Graph g = null;
int n = 0;
try {
Scanner scan = new Scanner(new File(args[0]));
g = AbstractGraph.createGraph(scan, true, "List");
n = g.getNumV();
} catch (IOException ex) {
ex.printStackTrace();
System.exit(1);
// Error
}
// Perform depth-first search.
DepthFirstSearch dfs = new DepthFirstSearch(g);
int[] dOrder = dfs.getDiscoveryOrder();
int[] fOrder = dfs.getFinishOrder();
System.out.println("Discovery and finish order");
for (int i = 0; i < n; i++) {
System.out.println(dOrder[i] + " " + fOrder[i]);
}
}
EXERCISES FOR SECTION 10.4
SELF-CHECK
1. Show the breadth-first search trees for the following graphs.
2. Show the depth-first search trees for the graphs in Exercise 1 above.
PROGRAMMING
Provide all accessor methods for class DepthFirstSearch and the constructor that specifies the order of start vertices.
Implement method depthFirstSearch without using recursion. Hint: Use a stack to save the parent of the current vertex when you start to search one of its adjacent vertices.
10.5 Applications of Graph Traversals
CASE STUDY Shortest Path through a Maze
Problem
We want to design a program that will find the shortest path through a maze. In Chapter 5, we showed how to write a recursive program that found a solution to a maze. This program used a backtracking algorithm that visited alternate paths. When it found a dead end, it backed up and tried another path, and eventually it found a solution.
Figure 10.21 shows a maze solution generated by this recursive program. The light-gray cells are barriers in the maze. The white squares show the solution path, the black squares show the squares that were visited but rejected, and the dark-gray squares were not visited. As you can see, the program did not find an optimal solution. (This is a consequence of the program advancing the solution path to the south before attempting to advance it to the east.) We want to find the shortest path, defined as the one with the fewest decision points in it.
image
FIGURE 10.21 Recursive Solution to a Maze
Analysis
We can represent the maze shown in Figure 10.21 by a graph, where we place a node at each decision point and at each dead end, as shown in Figure 10.22.
image
FIGURE 10.22 Graph Representation of the Maze in Figure 10.21
Now that we have the maze represented as a graph, we need to find the shortest path from the start point (vertex 0) to the end point (vertex 12). The breadth-first search method will return the shortest path from each vertex to its parent (the array of parent vertices), and we can use this array to find the shortest path to the end point. Recall that our shortest path will contain the smallest number of vertices, but not necessarily the smallest number of cells, in the path.
Design
Your program will need the following data structures:
An external representation of the maze, consisting of the number of vertices and the edges.
An object of a class that implements the Graph interface.
An array to hold the predecessors returned from the breadthFirstSearch method.
A stack to reverse the path.
The algorithm is as follows:
1. Read in the number of vertices and create the graph object.
2. Read in the edges and insert the edges into the graph.
3. Call the breadthFirstSearch method with this graph and the starting vertex as its argument. The method returns the array parent.
4. Start at v, the end vertex.
5. while v is not –1
6. Push v onto the stack.
7. Set v to parent[v].
8. while the stack is not empty
9. Pop a vertex off the stack and output it.
Implementation
Listing 10.5 shows the program. We assume that the graph that represents the maze is stored in a text file. The first line of this file contains the number of vertices. The edges are on subsequent lines. The method loadEdgesFromFile reads the source and destination vertices and inserts the edge into the graph. The rest of the code follows the algorithm.
LISTING 10.5
Program to Solve a Maze Using a Breadth-First Search
import java.io.*;
import java.util.*;
/** Program to solve a maze represented as a graph.
This program performs a breadth-first search of the graph
to find the "shortest" path from the start vertex to the
end. It is assumed that the start vertex is 0, and the
end vertex is numV-1.
*/
public class Maze {
/** Main method to solve the maze.
@pre args[0] contains the name of the input file.
@param args Command line argument
*/
public static void main(String[] args) {
int numV = 0; // The number of vertices.
Graph theMaze = null;
// Load the graph data from a file.
try {
Scanner scan = new Scanner(new File(args[0]));
theMaze = AbstractGraph.createGraph(scan, false, "List");
numV = theMaze.getNumV();
} catch (IOException ex) {
System.err.println("IO Error while reading graph");
System.err.println(ex.toString());
System.exit(1);
}
// Perform breadth-first search.
int parent[] = BreadthFirstSearch.breadthFirstSearch(theMaze, 0);
// Construct the path.
Deque<Integer> thePath = new ArrayDeque<>();
int v = numV - 1;
while (parent[v] != -1) {
thePath.push(v);
v = parent[v];
}
// Output the path.
System.out.println("The Shortest path is:");
while (!thePath.isEmpty()) {
System.out.println(thePath.pop());
}
}
}
Testing
Test this program with a variety of mazes. Use mazes for which the original program finds the shortest path and mazes for which it does not. For the graph shown in Figure 10.23, the shortest path from 0 to 12 is 0 → 1 → 2 → 8 → 12.
image
FIGURE 10.23 Solution to Maze in Figure 10.21
CASE STUDY Topological Sort of a Graph
Problem
There are many problems in which one activity cannot be started before another one has been completed. One that you may have already encountered is determining the order in which you can take courses. Some courses have prerequisites. Some have more than one prerequisite. Furthermore, the prerequisites may have prerequisites. Figure 10.24 shows the courses and prerequisites of a Computer Science program at the authors' university.
image
FIGURE 10.24 Prerequisites for a Computer Science Program
Graphs such as the one shown in Figure 10.24 are known as directed acyclic graphs (DAGs). They are directed graphs that contain no cycles; that is, there are no loops, so once you pass through a vertex, there is no path back to that vertex. Figure 10.25 shows another example of a DAG.
image
FIGURE 10.25 Example of a DAG
A topological sort of the vertices of a DAG is an ordering of the vertices such that if (u, v) is an edge, then u appears before v. This must be true for all edges. For example, 0, 1, 2, 3, 4, 5, 6, 7, 8 is a valid topological sort of the graph in Figure 10.25, but 0, 1, 5, 3, 4, 2, 6, 7, 8 is not because 2 → 5 is an edge, but 5 appears before 2. There are many valid paths through the prerequisite graph and many valid topological sorts. Another valid topological sort is 0, 3, 1, 4, 6, 2, 5, 7, 8.
Analysis
If there is an edge from u to v in a DAG, then if we perform a depth-first search of this graph, the finish time of u must be after the finish time of v. When we return to u, either v has not been visited or it has finished. It is not possible that v would be visited but not finished, because if it were possible, we would discover u on a path that had passed through v. That would mean that there is a loop or cycle in the graph.
For example, in Figure 10.25, we could start the depth-first search at 0, then visit 4, followed by 6, followed by 8. Then, returning to 4, we would have to visit 7 before returning to 0. Then we would visit 1, and from 1 we would see that 4 has finished. Alternatively, we could start at 0 and then go to 1, and we would see that 4 has not been visited. What we cannot have happen is that we start at 0, then visit 4, and eventually get to 1 before finishing 4.
Design
If we perform a depth-first search of a graph and then order the vertices by the inverse of their finish order, we will have one topological sort of a DAG. The topological sort produced by listing the vertices in the inverse of their finish order after a depth-first search of the graph in Figure 10.25 is 0, 3, 1, 4, 6, 2, 5, 7, 8.
Algorithm for Topological Sort
Read the graph from a data file.
Perform a depth-first search of the graph.
List the vertices in reverse of their finish order.
Implementation
We can use our DepthFirstSearch class to implement this algorithm. Listing 10.6 shows a program that does this. It begins by reading the graph from an input file. It then creates a DepthFirstSearch object dfs. The constructor of the DepthFirstSearch class performs the depth-first search and saves information about the graph. We then call the getFinishOrder method to get the vertices in the order in which they finished. If we output this array starting at numVertices – 1, we will obtain the topological sort of the graph.
LISTING 10.6
TopologicalSort.java
import java.util.*;
/** This program outputs the topological sort of a directed graph
that contains no cycles.
*/
public class TopologicalSort {
/** The main method that performs the topological sort.
@pre arg[0] contains the name of the file
that contains the graph. It has no cycles.
@param args The command line arguments
*/
public static void main(String[] args) {
Graph theGraph = null;
int numVertices = 0;
try {
// Connect Scanner to input file.
Scanner scan = new Scanner(new File(args[0]));
// Load the graph data from a file.
theGraph = AbstractGraph.createGraph(scan, true, "List");
numVertices = theGraph.getNumV();
} catch (Exception ex) {
ex.printStackTrace();
System.exit(1);
// Error exit.
}
// Perform the depth-first search.
DepthFirstSearch dfs = new DepthFirstSearch(theGraph);
// Obtain the finish order.
int[] finishOrder = dfs.getFinishOrder();
// Print the vertices in reverse finish order.
System.out.println("The Topological Sort is");
for (int i = numVertices - 1; i >= 0; i--) {
System.out.println(finishOrder[i]);
}
}
}
Testing
Test this program using several different graphs. Use sparse graphs and dense graphs. Make sure that each graph you try has no loops or cycles. If it does, the algorithm may display an invalid output.
EXERCISES FOR SECTION 10.5
SELF-CHECK
Draw the depth-first search tree of the graph in Figure 10.24 and then list the vertices in reverse finish order.
List some alternative topological sorts for the graph in Figure 10.24.
10.6 Algorithms Using Weighted Graphs
Finding the Shortest Path from a Vertex to All Other Vertices
The breadth-first search discussed in Section 10.4 found the shortest path from the start vertex to all other vertices, assuming that the length of each edge was the same. We now consider the problem of finding the shortest path where the length of each edge may be different—that is, in a weighted directed graph such as that shown in Figure 10.26. The computer scientist Edsger W. Dijkstra developed an algorithm, now called Dijkstra's algorithm (“A Note on Two Problems in Connection with Graphs,” Numerische Mathematik, Vol. 1 [1959], pp. 269–271), to solve this problem. This algorithm makes the assumption that all of the edge values are positive.
image
FIGURE 10.26 Weighted Directed Graph
For Dijkstra's algorithm, we need two sets, S and V–S, and two arrays, d and p. S will contain the vertices for which we have computed the shortest distance, and V–S will contain the vertices that we still need to process. The entry d[v] will contain the shortest distance from s to v, and p[v] will contain the predecessor of v in the path from s to v.
We initialize S by placing the start vertex, s, into it. We initialize V–S by placing the remaining vertices into it. For each v in V–S, we initialize d by setting d[v] equal to the weight of the edge w(s, v) for each vertex, v, adjacent to s and to ∞ for each vertex that is not adjacent to s. We initialize p[v] to s for each v in V–S.
For example, given the graph shown in Figure 10.26, the set S would initially be {0}, and V–S would be {1, 2, 3, 4}. The arrays d and p would be defined as follows.
v d[v] p[v]
1 10 0
2 ∞ 0
3 30 0
4 100 0
The first row shows that the distance from vertex 0 to vertex 1 is 10 and that vertex 0 is the predecessor of vertex 1. The second row shows that vertex 2 is not adjacent to vertex 0.
We now find the vertex u in V–S that has the smallest value of d[u]. Using our example, this is 1. We now consider the vertices v that are adjacent to u. If the distance from s to u (d[u]) plus the distance from u to v (i.e., w(u, v)) is smaller than the known distance from s to v, d[v], then we update d[v] to be d[u] + w(u, v), and we set p[v] to u. In our example, the value of d[1] is 10, and w(1, 2) is 50. Since 10 + 50 = 60 is less than ∞, we set d[2] to 60 and p[2] to 1. We remove 1 from V–S and place it into S. We repeat this until V–S is empty.
After the first pass through this loop, S is {0, 1}, V–S is {2, 3, 4}, and d and p are as follows:
v d[v] p[v]
1 10 0
2 60 1
3 30 0
4 100 0
We again select u from V–S with the smallest d[u]. This is now 3. The adjacent vertices to 3 are 2 and 4. The distance from 0 to 3, d[3], is 30. The distance from 3 to 2 is 20. Because 30 + 20 = 50 is less than the current value of d[2], 60, we update d[2] to 50 and change p[2] to 3. Also, because 30 + 60 = 90 is less than 100, we update d[4] to 90 and set p[4] to 3.
Now S is {0, 1, 3}, and V–S is {2, 4}. The arrays d and p are as follows:
v d[v] p[v]
1 10 0
2 50 3
3 30 0
4 90 3
Next, we select vertex 2 from V–S. The only vertex adjacent to 2 is 4. Since d[2] + w(2, 4) = 50 + 10 = 60 is less than d[4], 90, we update d[4] to 60 and p[4] to 2. Now S is {0, 1, 2, 3}, V–S is {4}, and d and p are as follows:
v d[v] p[v]
1 10 0
2 50 3
3 30 0
4 60 2
Finally, we remove 4 from V–S and find that it has no adjacent vertices. We are now done. The array d shows the shortest distances from the start vertex to all other vertices, and the array p can be used to determine the corresponding paths. For example, the path from vertex 0 to vertex 4 has a length of 60, and it is the reverse of 4, 2, 3, 0; therefore, the shortest path is 0 → 3 → 2 → 4.
Dijkstra's Algorithm
1. Initialize S with the start vertex, s, and V–S with the remaining vertices.
2. for all v in V–S
3. Set p[v] to s.
4. if there is an edge (s, v)
5. Set d[v] to w(s, v).
else
6. Set d[v] to ∞.
7. while V–S is not empty
8. for all u in V–S, find the smallest d[u].
9. Remove u from V–S and add u to S.
10. for all v adjacent to u in V–S
11. if d[u] + w(u, v) is less than d[v]
12. Set d[v] to d[u] + w(u, v).
13. Set p[v] to u.
Analysis of Dijkstra's Algorithm
Step 1 requires |V| steps.
The loop at Step 2 will be executed |V – 1| times.
The loop at Step 7 will also be executed |V – 1| times.
Within the loop at Step 7, we have to consider Steps 8 and 9. For these steps, we will have to search each value in V–S. This decreases each time through the loop at Step 7, so we will have |V| – 1 + |V| – 2 + · · · 1. This is O(|V|2). Therefore, Dijkstra's algorithm as stated is O(|V|2). We will look at possible improvements to this for sparse graphs when we discuss a similar algorithm in the next subsection.
Implementation
Listing 10.7 provides a straightforward implementation of Dijkstra's algorithm using HashSet vMinusS to represent set V–S. We chose to implement the algorithm as a static method with the inputs (the graph and starting point) and outputs (predecessor and distance array) passed through parameters. An alternative approach would be to make them data fields in a class that contained this method. We use iterators to traverse vMinusS.
If we used an adjacency list representation for the graph (i.e., class ListGraph, described earlier), then we would code Step 10 (update the distances) to iterate through the edges adjacent to vertex u, and then update the distance if the destination vertex was in vMinusS. The modified code follows:
// Update the distances.
Iterator<Edge> edgeIter = graph.edgeIterator(u);
while (edgeIter.hasNext()) {
Edge edge = edgeIter.next();
int v = edge.getDest();
if (vMinusS.contains(new Integer(v)) {
double weight = edge.getWeight();
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pred[v] = u;
}
}
}
LISTING 10.7
Dijkstra's Shortest-Path Algorithm
/** Dijkstra's Shortest-Path algorithm.
@param graph The weighted graph to be searched
@param start The start vertex
@param pred Output array to contain the predecessors in the shortest path
@param dist Output array to contain the distance in the shortest path
*/
public static void dijkstrasAlgorithm(Graph graph, int start, int[] pred,
double[] dist) {
int numV = graph.getNumV();
HashSet<Integer> vMinusS = new HashSet<>(numV);
// Initialize V–S.
for (int i = 0; i < numV; i++) {
if (i != start) {
vMinusS.add(i);
}
}
// Initialize pred and dist.
for (int v : vMinusS) {
pred[v] = start;
dist[v] = graph.getEdge(start, v).getWeight();
}
// Main loop
while (vMinusS.size() != 0) {
// Find the value u in V–S with the smallest dist[u].
double minDist = Double.POSITIVE_INFINITY;
int u = -1;
for (int v : vMinusS) {
if (dist[v] < minDist) {
minDist = dist[v];
u = v;
}
}
// Remove u from vMinusS.
vMinusS.remove(u);
// Update the distances.
for (int v : vMinusS) {
if (graph.isEdge(u, v)) {
double weight = graph.getEdge(u, v).getWeight();
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pred[v] = u;
}
}
}
}
Minimum Spanning Trees
A spanning tree is a subset of the edges of a graph such that there is only one edge between each vertex, and all of the vertices are connected. If we have a spanning tree for a graph, then we can access all the vertices of the graph from the start node. The cost of a spanning tree is the sum of the weights of the edges. We want to find the minimum spanning tree or the spanning tree with the smallest cost. For example, if we want to start up our own long-distance phone company and need to connect the cities shown in Figure 10.4, finding the minimum spanning tree would allow us to build the cheapest network.
We will discuss the algorithm published by R. C. Prim (“Shortest Connection Networks and Some Generalizations,” Bell System Technical Journal, Vol. 36 [1957], pp. 1389–1401) for finding the minimum spanning tree of a graph. It is very similar to Dijkstra's algorithm, but Prim published his algorithm in 1957, 2 years before Dijkstra's paper that contains an algorithm for finding the minimum spanning tree that is essentially the same as Prim's as well as the previously discussed algorithm for finding the shortest paths.
Overview of Prim's Algorithm
The vertices are divided into two sets: S, the set of vertices in the spanning tree, and V–S, the remaining vertices. As in Dijkstra's algorithm, we maintain two arrays: d[v] will contain the length of the shortest edge from a vertex in S to the vertex v that is in V–S, and p[v] will contain the source vertex for that edge. The only difference between the algorithm to find the shortest path and the algorithm to find the minimum spanning tree is the contents of d[v]. In the algorithm to find the shortest path, d[v] contains the total length of the path from the starting vertex. In the algorithm to find the minimum spanning tree, d[v] contains only the length of the final edge. We show the essentials of Prim's algorithm next.
Prim's Algorithm for Finding the Minimum Spanning Tree
1. Initialize S with the start vertex, s, and V–S with the remaining vertices.
2. for all v in V–S
3. Set p[v] to s.
4. if there is an edge (s, v)
5. Set d[v] to w(s, v).
else
6. Set d[v] to ∞.
7. while V–S is not empty
8. for all u in V–S, find the smallest d[u].
9. Remove u from V–S and add it to S.
10. Insert the edge (u, p[u]) into the spanning tree.
11. for all v in V–S
12. if w(u, v) < d[v]
13. Set d[v] to w(u, v).
14. Set p[v] to u.
In the array d, d[v] contains the length of the shortest known (previously examined) edge from a vertex in S to the vertex v, while v is a member of V–S. In the array p, the value p[v] is the source vertex of this shortest edge. When v is removed from V–S, we no longer update these entries in d and p.
EXAMPLE 10.2
Consider the graph shown in Figure 10.27. We initialize S to {0} and V–S to {1, 2, 3, 4, 5}. The smallest edge from u to v, where u is in S and v is in V–S, is the edge (0, 2). We add this edge to the spanning tree and add 2 to S (see Figure 10.28(a)). The set S is now {0, 2} and V–S is {1, 3, 4, 5}. We now have to consider all of the edges (u, v), where u is either 0 or 2, and v is 1, 3, 4, or 5 (there are eight possible edges). The smallest one is (2, 5). We add this to the spanning tree, and S now is {0, 2, 5} and V–S is {1, 3, 4} (see Figure 10.28(b)). The next smallest edge is (5, 3). We insert that into the tree and add 3 to S (see Figure 10.28(c)). Now V–S is {1, 4}. The smallest edge is (2, 1). After adding this edge (see Figure 10.28(d)), we are left with V–S being {4}. The smallest edge to 4 is (1, 4). This is added to the tree, and the spanning tree is complete (see Figure 10.28(e)).
image
FIGURE 10.27 Graph for Example 10.2
image
FIGURE 10.28 Building a Minimum Spanning Tree Using Prim's Algorithm
Analysis of Prim's Algorithm
Step 8 is O(|V|). Because this is within the loop at Step 7, it will be executed O(|V|) times for a total time of O(|V|2). Step 11 is O(|Eu|), the number of edges that originate at u. Because Step 11 is inside the loop of Step 7, it will be executed for all vertices; thus, the total is O(|E|). Because |V|2 is greater than |E|, the overall cost of the algorithm is O(|V|2).
By using a priority queue to hold the edges from S to V–S, we can improve on this algorithm. Then Step 8 is O(log n), where n is the size of the priority queue. In the worst case, all of the edges are inserted into the priority queue, and the overall cost of the algorithm is then O(|E| log |V|). We say that the algorithm is O(|E| log |V|) instead of saying that it is O(|E| log |E|), even though the maximum size of the priority queue is |E|, because |E| is bounded by |V|2 and log |V|2 is 2 × log |V|.
For a dense graph, where |E| is approximately |V|2, this is not an improvement; however, for a sparse graph, where |E| is significantly less than |V|2, it is. Furthermore, computer science researchers have developed improved priority queue implementations that give O(|E| + |V| log |V|) or better performance.
Implementation
Listing 10.8 shows an implementation of Prim's algorithm using a priority queue to hold the edges from S to V–S. The arrays p and d given in the algorithm description above are not needed because the priority queue contains complete edges. For a given vertex d, if a shorter edge is discovered, we do not remove the entry containing the longer edge from the priority queue. We merely insert new edges as they are discovered. Therefore, when the next shortest edge is removed from the priority queue, it may have a destination that is no longer in V–S. In that case, we continue to remove edges from the priority queue until we find one with a destination that is still in V–S. This is done with the following loop:
do {
edge = pQ.remove();
dest = edge.getDest();
} while(!vMinusS.contains(dest));
LISTING 10.8
Prim's Minimum Spanning Tree Algorithm
/** Prim's Minimum Spanning Tree algorithm.
@param graph The weighted graph to be searched
@param start The start vertex
@return An ArrayList of edges that forms the MST
*/
public static ArrayList<Edge> primsAlgorithm(Graph graph, int start) {
ArrayList<Edge> result = new ArrayList<>();
int numV = graph.getNumV();
// Use a HashSet to represent V–S.
Set<Integer> vMinusS = new HashSet<>(numV);
// Declare the priority queue.
Queue<Edge> pQ = new PriorityQueue<>(numV,
(e1, e2) -> Double.compare(e1.getWeight(), e2.getWeight()));
// Initialize V–S.
for (int i = 0; i < numV; i++) {
if (i != start) {
vMinusS.add(i);
}
}
int current = start;
// Main loop
while (vMinusS.size() != 0) {
// Update priority queue.
Iterator<Edge> iter = graph.edgeIterator(current);
while (iter.hasNext()) {
Edge edge = iter.next();
int dest = edge.getDest();
if (vMinusS.contains(dest)) {
pQ.add(edge);
}
}
// Find the shortest edge whose source is in S and
// destination is in V–S.
int dest = -1;
Edge edge = null;
do {
edge = pQ.remove();
dest = edge.getDest();
} while(!vMinusS.contains(dest));
// Take dest out of vMinusS.
vMinusS.remove(dest);
// Add edge to result.
result.add(edge);
// Make this the current vertex.
current = dest;
}
return result;
EXERCISES FOR SECTION 10.6
SELF-CHECK
Trace the execution of Dijkstra's algorithm to find the shortest path from Philadelphia to the other cities shown in the following graph.
image
Trace the execution of Dijkstra's algorithm to find the shortest paths from vertex 0 to the other vertices in the following graph.
image
Trace the execution of Prim's algorithm to find the minimum spanning tree for the graph shown in Exercise 2.
Trace the execution of Prim's algorithm to find the minimum spanning tree for the graph shown in Exercise 1.
Chapter Review
A graph consists of a set of vertices and a set of edges. An edge is a pair of vertices. Graphs may be either undirected or directed. Edges may have a value associated with them known as the weight.
In an undirected graph, if {u, v} is an edge, then there is a path from vertex u to vertex v, and vice versa.
In a directed graph, if (u, v) is an edge, then (v, u) is not necessarily an edge.
If there is an edge from one vertex to another, then the second vertex is adjacent to the first. A path is a sequence of adjacent vertices. A path is simple if the vertices in the path are distinct except, perhaps, for the first and last vertex, which may be the same. A cycle is a path in which the first and last vertexes are the same.
A graph is considered connected if there is a path from each vertex to every other vertex.
A tree is a special case of a graph. Specifically, a tree is a connected graph that contains no cycles.
Graphs may be represented by an array of adjacency lists. There is one list for each vertex, and the list contains the edges that originate at this vertex.
Graphs may be represented by a two-dimensional square array called an adjacency matrix. The entry [u][v] will contain a value to indicate that an edge from u to v is present or absent.
A breadth-first search of a graph finds all vertices reachable from a given vertex via the shortest path, where the length of the path is based on the number of vertices in the path.
A depth-first search of a graph starts at a given vertex and then follows a path of unvisited vertices until it reaches a point where there are no unvisited vertices that are reachable. It then backtracks until it finds an unvisited vertex, and then continues along the path to that vertex.
A topological sort determines an order for starting activities that are dependent on the completion of other activities (prerequisites). The finish order derived from a depth-first traversal represents a topological sort.
Dijkstra's algorithm finds the shortest path from a start vertex to all other vertices, where the distance from one vertex to another is determined by the weight of the edge between them.
Prim's algorithm finds the minimum spanning tree for a graph. This consists of the subset of the edges of a connected graph whose sum of weights is the minimum and the graph consisting of only the edges in the subset is still connected.
User-Defined Classes and Interfaces in This Chapter
AbstractGraph ListGraph
BreadthFirstSearch MatrixGraph
DepthFirstSearch MatrixGraph.Iter
Edge Maze
Graph TopologicalSort
Quick-Check Exercises
For the following graph:
List the vertices and edges.
True or false: The path 0, 1, 4, 6, 3 is a simple path.
True or false: The path 0, 3, 1, 4, 6, 3, 2 is a simple path.
True or false: The path 3, 1, 2, 4, 7, 6, 3 is a cycle.
image
Identify the connected components in the following graph.
image
For the following graph:
List the vertices and edges.
Does this graph contain any cycles?
image
Show the adjacency matrices for the graphs shown in Questions 1, 2, and 3.
Show the adjacency lists for the graphs shown in Questions 1, 2, and 3.
Show the breadth-first search tree for the graph shown in Question 1, starting at vertex 0.
Show the depth-first search tree for the graph shown in Question 3, starting at vertex 0.
Show a topological sort of the vertices in the graph shown in Question 3.
In the following graph, find the shortest path from 0 to all other vertices.
image
In the following graph, find the minimum spanning tree.
image
Review Questions
What are the different types of graphs?
What are the different types of paths?
What are two common methods for representing graphs? Can you think of other methods?
What is a breadth-first search? What can it be used for?
What is a depth-first search? What can it be used for?
Under what circumstances are the paths found by Dijkstra's algorithm not unique?
Under what circumstances is the minimum spanning tree unique?
What is a topological sort?
Programming Projects
Design and implement the MatrixGraph class.
Rewrite method dijkstrasAlgorithm to use a priority queue as we did for method primsAlgorithm. When inserting edges into the priority queue, the weight is replaced by the total distance from the source vertex to the destination vertex. The source vertex, however, remains unchanged as it is the predecessor in the shortest path.
In both Prim's algorithm and Dijkstra's algorithm, edges are retained in the priority queue, even though a shorter edge to a given destination vertex has been found. This can be avoided, and thus performance improved, by using a ModifiablePriorityQueue. Extend the PriorityQueue class described in Chapter 6 as follows:
/** A ModifiablePriorityQueue stores Comparable objects. Items
may be inserted in any order. They are removed in priority
order, with the smallest being removed first, based on the
compareTo method. The insert method will return a value
known as a locator. The locator may be used to replace a
value in the priority queue.
*/
public class ModifiablePriorityQueue<E extends Comparable<E>>
extends PriorityQueue<E> {
/** Insert an item into the priority queue.
@param obj The item to be inserted
@return A locator to the item
*/
int insert(E obj);
/** Remove the smallest item in the priority queue.
@return The smallest item in the priority queue
*/
E poll();
/** Replace the item at the specified location.
@param loc The locator value of the current item
@param newValue The new value
*/
void replaceItem(int loc, E newValue);
. . .
Implement Dijkstra's algorithm using the ModifiablePriorityQueue.
Implement Prim's algorithm using the ModifiablePriortyQueue.
A maze can be constructed from a series of concentric circles. Between the circles there are walls placed, and around the circles there are doors. The walls divide the areas between the circles into chambers, and the doors permit movement between chambers. The positions of the doors and walls are given in degrees measured counterclockwise from the horizontal. For example, the maze shown on the left can be described as follows:
image
Number of circles 4
Position of doors Outer circle 85–90
Next inner circle 26–40, 135–146, 198–215, 305–319
Next inner circle 67–90, 161–180, 243–256, 342–360
Innermost circle 251–288
Position of walls Outer ring 45, 135, 300
Middle ring 0, 100, 225, 270
Inner ring 65, 180
Write a program that inputs a description of a maze in this format and finds the shortest path from the outside to the innermost circle. The shortest path is the one that goes through the smallest number of chambers.
In Chapter 5 we discussed the class MazeTest, which reads a rectangular maze as a sequence of lines consisting of 0s and 1s, where a 0 represents an open square and a 1 represents a closed one. For example, the maze shown in Figure 10.21 and reproduced here has the following input file:
011111111111111111111111
000000000000000000000001
011111111111111011111101
011111100000001011111101
011111101111111011000001
000000000000000011011011
110111101101111011011011
110111101101111011011011
110111101101000011011011
110111101101111111011011
110111101100000000011011
110000001101111111111011
111101111100000000001011
111101111111111111101000
111100000000000000001110
111111111111111111111110
image
Write a program that reads input in this format and finds the shortest path, where the distance along a path is defined by the number of squares covered.
A third possible representation of a graph is to use the TreeSet class to contain the edges. By defining a comparator that compares first on the source vertex and then the destination vertex, we can use the subSet method to create a view that contains only edges originating at a specified vertex and then use the iterator of that view to iterate through edges. Design and implement a class that meets the requirements of the Graph interface and uses a TreeSet to hold the edges.
Answers to Quick-Check Exercises
1.
Vertices: {0, 1, 2, 3, 4, 5, 6, 7}
Edges: {{0, 1}, {0, 3}, {1, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {3, 6}, {4, 6}, {4, 7}, {5, 6}, {6, 7}}
True
False
True
2. The connected components are {0, 3, 5, 6}, {1, 4, 7}, and {2}.
3.
Vertices: {0, 1, 2, 3, 4, 5, 6, 7}
Edges: {(0, 1), (0, 3), (0, 5), (1, 2), (2, 4), (3, 4), (4, 7), (5, 3), (5, 6), (6, 7)}
The graph contains no cycles.
4. For the graph shown in Question 1:
image
For Question 2:
image
For Question 3:
image
For Question 1:
[0] → 1 → 3
[1] → 0 → 2 → 3 → 4
[2] → 1 → 4
[3] → 0 → 1 → 5 → 6
[4] → 1 → 2 → 6 → 7
[5] → 3 → 6
[6] → 3 → 4 → 5 → 7
[7] → 4 → 6
For Question 2:
[0] → 3 → 5
[1] → 4
[2] →
[3] → 0 → 5 → 6
[4] → 1 → 7
[5] → 0 → 3
[6] → 3
[7] → 4
For Question 3:
[0] → 1 → 3 → 5
[1] → 2
[2] → 4
[3] → 4
[4] → 7
[5] → 3 → 6
[6] → 7
[7] →
6.
image
7.
image
8. 8.0, 5, 6, 3, 1, 2, 4, 7
9.
Vertex Distance Path
1 10 0 → 1
2 25 0 → 1 → 2
3 30 0 → 3 (or 0 → 5 → 3)
4 30 0 → 1 → 2 → 4
5 20 0 → 5
6 25 0 → 5 → 6
7 40 0 → 5 → 6 → 7 (or 0 → 1 → 2 → 4 → 7)
10.
image
