Java Reference
In-Depth Information
11.8
Projects
11.1 Design a format for storing graphs in files. Then implement two functions:
one to read a graph from a file and the other to write a graph to a file. Test
your functions by implementing a complete MST program that reads an undi-
rected graph in from a file, constructs the MST, and then writes to a second
file the graph representing the MST.
11.2 An undirected graph need not explicitly store two separate directed edges to
represent a single undirected edge. An alternative would be to store only a
single undirected edge (I, J) to connect Vertices I and J. However, what if the
user asks for edge (J, I)? We can solve this problem by consistently storing
the edge such that the lesser of I and J always comes first. Thus, if we have
an edge connecting Vertices 5 and 3, requests for edge (5, 3) and (3, 5) both
map to (3, 5) because 3 < 5.
Looking at the adjacency matrix, we notice that only the lower triangle of
the array is used. Thus we could cut the space required by the adjacency
matrix from jVj
2
positions to jVj(jVj1)=2 positions. Read Section 12.2 on
triangular matrices. The re-implement the adjacency matrix representation
of Figure 11.6 to implement undirected graphs using a triangular array.
11.3 While the underlying implementation (whether adjacency matrix or adja-
cency list) is hidden behind the graph ADT, these two implementations can
have an impact on the efficiency of the resulting program. For Dijkstra's
shortest paths algorithm, two different implementations were given in Sec-
tion 11.4.1 that provide different ways for determining the next closest vertex
at each iteration of the algorithm. The relative costs of these two variants
depend on who sparse or dense the graph is. They might also depend on
whether the graph is implemented using an adjacency list or adjacency ma-
trix.
Design and implement a study to compare the effects on performance for
three variables: (i) the two graph representations (adjacency list and adja-
cency matrix); (ii) the two implementations for Djikstra's shortest paths alg-
orithm (searching the table of vertex distances or using a priority queue to
track the distances), and (iii) sparse versus dense graphs. Be sure to test your
implementations on a variety of graphs that are sufficiently large to generate
meaningful times.
11.4 The example implementations for DFS and BFS show calls to functions
PreVisit
and
PostVisit
. Re-implement the BFS and DFS functions
to make use of the visitor design pattern to handle the pre/post visit function-
ality.
11.5 Write a program to label the connected components for an undirected graph.
In other words, all vertices of the first component are given the first com-
ponent's label, all vertices of the second component are given the second
