Java程序辅导

School of Computer Science & Software Engineering
The University of Western Australia
Crawley, Western Australia, 6009.
CRICOS Provider Code: 00126G
CITS3210 Algorithms Laboratory sheet 2
These exercises are worth 2.5% of your final grade and are due at 5pm, Friday
August 31, 2012
Use the Graph, class provided on the unit web-page, to write a breadth-first search algorithm and
depth first search algorithm for directed graphs (as described in the lecture notes). The interface
Search is provided and you should implement it as a class SearchImp. You should complete the
following methods:
1. The method getConnectedTree should output an array specifying the parent vertex for
each vertex (or -1 if there is no parent), assuming a Breadth First Search.
2. The method getDistances should output an array specifying the distance each vertex is
from the starting vertex, or -1 if it is not reachable.
3. In the method, getTimes you should, assuming a depth first search, output the start and
finish times for each vertex.Given that the graph G has n vertices, the method getTimes(G)
should return an n× 2 array of integers. For example. if a = getTimes(G) then the start
time for vertex i is a[i][0] and the end time for vertex i is a[i][1].
4. A Strongly Connected Component of a directed graph G is a set of vertices V where there
is a path (of length 0 or more) from every vertex in V to every other vertex in V . A
directed graph can be decomposed into its strongly connected components using depth-
first search. The algorithm for finding strongly connected components in a directed graph
can be summarized as follows:
STRONGLY-CONNECTED-COMPONENT(G)
1. Call DFS(G) to compute the finishing time f [u] for each vertex u
2. Compute GT , where GT denotes the graph G having the directions of all its
edges reversed
3. Call DFS(GT ), but in the main loop of DFS, consider the vertices in order
of decreasing f [u] computed from Step 1
4. Output the vertices of each tree in the depth-first forest formed in Step 3 as
a separate strongly connected component
Implement this algorithm in the method getSCC(Graph g). This method should return a
partition of the vertices in the graph. For example, given the graph below the algorithm
should return the array
{0,0,2,3,4,5}
1
which defines the strongly connected components (0,1), (2), (3), (4), (5).
A test program, SearchTest, allows you to either read in a graph from a file, or generate a
random graph on which to perform a breadth-first search. The class then prints out the array
of parent vertices for the spanning tree, and their distances from the start vertex (assuming you
have implemented the algorithms correctly).
For specifying a program from the file you should use the following format for the input data
file:
6
0 1 1 1 0 0
1 0 1 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 1 0
where the first line is the total number of vertices. The numbers from the second line onward
are the entries of the n× n adjacency matrix. This corresponds to the graph:
0 1 5
423
You may assume that all the vertices are labelled as 0, 1, 2, · · · You may also assume that the
matrix is unweighted, i.e. if there is an edge (i, j) in the graph then (i, j) = 1 otherwise (i, j) = 0
in the matrix. However, your program should work for both directed and undirected graphs.
Note that as an automated marker is used you will not be able to include print statements,
java.util classes etc in your implementation. However, a test class SearchTest.java is available
for your convenience.
Submit only the file SearchImp.java to https://secure.csse.uwa.edu.au/run/cssubmit.
There is an automated script that will compile and run your code, and estimate your final mark.
This feedback ensures that you will not lose marks for small errors, but is no substitute for your
own thorough testing.
2