Java Reference
In-Depth Information
*28.5
(
Find paths
) Add a new method in
AbstractGraph
to find a path between two
vertices with the following header:
public
List<Integer> getPath(
int
u,
int
v);
The method returns a
List<Integer>
that contains all the vertices in a path
from
u
to
v
in this order. Using the BFS approach, you can obtain a shortest
path from
u
to
v
. If there isn't a path from
u
to
v
, the method returns
null
.
*28.6
(
Detect cycles
) Add a new method in
AbstractGraph
to determine whether
there is a cycle in the graph with the following header:
public boolean
isCyclic();
*28.7
(
Find a cycle
) Add a new method in
AbstractGraph
to find a cycle in the
graph with the following header:
public
List<Integer> getACycle(
int
u);
The method returns a
List
that contains all the vertices in a cycle starting from
u
. If the graph doesn't have any cycles, the method returns
null
.
**28.8
(
Test bipartite
) Recall that a graph is bipartite if its vertices can be divided into
two disjoint sets such that no edges exist between vertices in the same set. Add
a new method in
AbstractGraph
with the following header to detect whether
the graph is bipartite:
public boolean
isBipartite();
**28.9
(
Get bipartite sets
) Add a new method in
AbstractGraph
with the following
header to return two bipartite sets if the graph is bipartite:
public
List<List<Integer>> getBipartite();
The method returns a
List
that contains two sublists, each of which contains a
set of vertices. If the graph is not bipartite, the method returns
null
.
28.10
(
Find a shortest path
) Write a program that reads a connected graph from a
file. The graph is stored in a file using the same format specified in Program-
ming Exercise 28.1. Your program should prompt the user to enter the name of
the file, then two vertices, and should display a shortest path between the two
vertices. For example, for the graph in Figure 28.21a, a shortest path between
0
and
5
may be displayed as
0 1 3 5
.
Here is a sample run of the program:
Enter a file name: c:\exercise\GraphSample1.txt
Enter two vertices (integer indexes): 0 5
The number of vertices is 6
Vertex 0: (0, 1) (0, 2)
Vertex 1: (1, 0) (1, 3)
Vertex 2: (2, 0) (2, 3) (2, 4)
Vertex 3: (3, 1) (3, 2) (3, 4) (3, 5)
Vertex 4: (4, 2) (4, 3) (4, 5)
Vertex 5: (5, 3) (5, 4)
The path is 0 1 3 5
Search WWH ::
Custom Search