Java Reference
In-Depth Information
{
6
,
5
}, {
6
,
7
},
{
7
,
4
}, {
7
,
5
}, {
7
,
6
}, {
7
,
8
},
{
8
,
4
}, {
8
,
7
}, {
8
,
9
}, {
8
,
10
}, {
8
,
11
},
{
9
,
8
}, {
9
,
11
},
{
10
,
2
}, {
10
,
4
}, {
10
,
8
}, {
10
,
11
},
{
11
,
8
}, {
11
,
9
}, {
11
,
10
}
};
This representation is known as the
edge array
. The vertices and edges in Figure 28.3a can be
represented as follows:
edge array
String[] names = {
"Peter"
,
"Jane"
,
"Mark"
,
"Cindy"
,
"Wendy"
};
int
[][] edges = {{
0
,
2
}, {
1
,
2
}, {
2
,
4
}, {
3
,
4
}};
28.3.3 Representing Edges:
Edge
Objects
Another way to represent the edges is to define edges as objects and store the edges in a
java.util.ArrayList
. The
Edge
class can be defined as follows:
public class
Edge {
int
u;
int
v;
public
Edge(
int
u,
int
v) {
this
.u = u;
this
.v = v;
}
public boolean
equals(Object o) {
return
u == ((Edge)o).u && v == ((Edge)o).v;
}
}
For example, you can store all the edges in the graph in Figure 28.1 using the following list:
java.util.ArrayList<Edge> list =
new
java.util.ArrayList<>();
list.add(
new
Edge(
0
,
1
));
list.add(
new
Edge(
0
,
3
));
list.add(
new
Edge(
0
,
5
));
...
Storing
Edge
objects in an
ArrayList
is useful if you don't know the edges in advance.
While representing edges using an edge array or
Edge
objects in Section 28.3.2 and earlier
in this section may be intuitive for input, it's not efficient for internal processing. The next two
sections introduce the representation of graphs using
adjacency matrices
and
adjacency lists
.
These two data structures are efficient for processing graphs.
28.3.4 Representing Edges: Adjacency Matrices
Assume that the graph has
n
vertices. You can use a two-dimensional
n
n
matrix,
say
adjacencyMatrix
, to represent the edges. Each element in the array is
0
or
1
.
adjacencyMatrix[i][j]
is
1
if there is an edge from vertex
i
to vertex
j
; otherwise,
adjacencyMatrix[i][j]
is
0
. If the graph is undirected, the matrix is symmetric, because
adjacencyMatrix[i][j]
is the same as
adjacencyMatrix[j][i]
. For example, the
edges in the graph in Figure 28.1 can be represented using an
adjacency matrix
as follows:
*
adjacency matrix
int
[][] adjacencyMatrix = {
{
0
,
1
,
0
,
1
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
0
},
// Seattle
{
1
,
0
,
1
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
},
// San Francisco
Search WWH ::
Custom Search