Java Reference
In-Depth Information
implement all the methods defined in the
Graph
interface. For convenience, we assume the
graph is a simple graph, i.e., a vertex has no edge to itself and there are no parallel edges from
vertex
u
to
v
.
AbstractGraph
implements all the methods from
Graph
, and it does not introduce any
new methods except a convenient
addEdge(edge)
method that adds an
Edge
object to the
adjacency edge list.
UnweightedGraph
simply extends
AbstractGraph
with five construc-
tors for creating the concrete
Graph
instances.
Note
You can create a graph with any type of vertices. Each vertex is associated with an index,
which is the same as the index of the vertex in the vertices list. If you create a graph
without specifying the vertices, the vertices are the same as their indices.
vertices and their indices
Note
The
AbstractGraph
class implements all the methods in the
Graph
interface. So
why is it defined as abstract? In the future, you may need to add new methods to
the
Graph
interface that cannot be implemented in
AbstractGraph
. To make the
classes easy to maintain, it is desirable to define the
AbstractGraph
class as abstract.
why
AbstractGraph
?
Assume all these interfaces and classes are available. Listing 28.1 gives a test program that
creates the graph in Figure 28.1 and another graph for the one in Figure 28.3a.
L
ISTING
28.1
TestGraph.java
1
public class
TestGraph {
2
public static void
main(String[] args) {
3 String[] vertices = {
"Seattle"
,
"San Francisco"
,
"Los Angeles"
,
4
vertices
"Denver"
,
"Kansas City"
,
"Chicago"
,
"Boston"
,
"New York"
,
5
"Atlanta"
,
"Miami"
,
"Dallas"
,
"Houston"
};
6
7
// Edge array for graph in Figure 28.1
8
int
[][] edges = {
9 {
0
,
1
}, {
0
,
3
}, {
0
,
5
},
10 {
1
,
0
}, {
1
,
2
}, {
1
,
3
},
11 {
2
,
1
}, {
2
,
3
}, {
2
,
4
}, {
2
,
10
},
12 {
3
,
0
}, {
3
,
1
}, {
3
,
2
}, {
3
,
4
}, {
3
,
5
},
13 {
4
,
2
}, {
4
,
3
}, {
4
,
5
}, {
4
,
7
}, {
4
,
8
}, {
4
,
10
},
14 {
5
,
0
}, {
5
,
3
}, {
5
,
4
}, {
5
,
6
}, {
5
,
7
},
15 {
6
,
5
}, {
6
,
7
},
16 {
7
,
4
}, {
7
,
5
}, {
7
,
6
}, {
7
,
8
},
17 {
8
,
4
}, {
8
,
7
}, {
8
,
9
}, {
8
,
10
}, {
8
,
11
},
18 {
9
,
8
}, {
9
,
11
},
19 {
10
,
2
}, {
10
,
4
}, {
10
,
8
}, {
10
,
11
},
20 {
11
,
8
}, {
11
,
9
}, {
11
,
10
}
21 };
22
23 Graph<String> graph1 =
new
UnweightedGraph<>(vertices, edges);
24 System.out.println(
"The number of vertices in graph1: "
25 + graph1.getSize());
26 System.out.println(
"The vertex with index 1 is "
27 + graph1.getVertex(
1
));
28 System.out.println(
"The index for Miami is "
+
29 graph1.getIndex(
"Miami"
));
30 System.out.println(
"The edges for graph1:"
);
31
edges
create a graph
number of vertices
get vertex
get index
graph1.printEdges();
print edges
32
33
// List of Edge objects for graph in Figure 28.3a
34 String[] names = {
"Peter"
,
"Jane"
,
"Mark"
,
"Cindy"
,
"Wendy"
};
Search WWH ::
Custom Search