Java Reference
In-Depth Information
{
0
,
1
,
0
,
1
,
1
,
1
,
0
,
0
,
0
,
0
,
0
,
0
},
// Los Angeles
{
1
,
1
,
1
,
0
,
1
,
1
,
0
,
0
,
0
,
0
,
0
,
0
},
// Denver
{
0
,
0
,
1
,
1
,
0
,
1
,
0
,
1
,
1
,
0
,
1
,
0
},
// Kansas City
{
1
,
0
,
0
,
1
,
1
,
0
,
1
,
1
,
0
,
0
,
0
,
0
},
// Chicago
{
0
,
0
,
0
,
0
,
0
,
1
,
0
,
1
,
0
,
0
,
0
,
0
},
// Boston
{
0
,
0
,
0
,
0
,
1
,
1
,
1
,
0
,
1
,
0
,
0
,
0
},
// New York
{
0
,
0
,
0
,
1
,
1
,
0
,
0
,
1
,
0
,
1
,
1
,
1
},
// Atlanta
{
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
1
,
0
,
0
,
1
},
// Miami
{
0
,
0
,
1
,
0
,
1
,
0
,
0
,
0
,
1
,
0
,
0
,
1
},
// Dallas
{
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
1
,
1
,
1
,
0
}
// Houston
};
Note
Since the matrix is symmetric for an undirected graph, to save storage you can use a
ragged array.
ragged array
The adjacency matrix for the directed graph in Figure 28.3a can be represented as follows:
int
[][] a = {{
0
,
0
,
1
,
0
,
0
},
// Peter
{
0
,
0
,
1
,
0
,
0
},
// Jane
{
0
,
0
,
0
,
0
,
1
},
// Mark
{
0
,
0
,
0
,
0
,
1
},
// Cindy
{
0
,
0
,
0
,
0
,
0
}
// Wendy
};
28.3.5 Representing Edges: Adjacency Lists
You can represent edges using
adjacency vertex lists
or
adjacency edge lists
. An adjacency
vertex list for a vertex
i
contains the vertices that are adjacent to
i
and an adjacency edge list
for a vertex
i
contains the edges that are adjacent to
i
. You may define an array of lists. The
array has
n
entries, and each entry is a list. The adjacency vertex list for vertex
i
contains all
the vertices
j
such that there is an edge from vertex
i
to vertex
j
. For example, to represent the
edges in the graph in Figure 28.1, you can create an array of lists as follows:
adjacency vertex lists
adjacency edge lists
java.util.List<Integer>[] neighbors =
new
java.util.List[
12
];
neighbors[0]
contains all vertices adjacent to vertex
0
(i.e., Seattle),
neighbors[1]
con-
tains all vertices adjacent to vertex
1
(i.e., San Francisco), and so on, as shown in Figure 28.6.
To represent the adjacency edge lists for the graph in Figure 28.1, you can create an array
of lists as follows:
java.util.List<Edge>[] neighbors =
new
java.util.List[
12
];
neighbors[0]
contains all edges adjacent to vertex
0
(i.e., Seattle),
neighbors[1]
con-
tains all edges adjacent to vertex
1
(i.e., San Francisco), and so on, as shown in Figure 28.7.
Note
You can represent a graph using an adjacency matrix or adjacency lists. Which one is
better? If the graph is dense (i.e., there are a lot of edges), using an adjacency matrix is
preferred. If the graph is very sparse (i.e., very few edges), using adjacency lists is better,
because using an adjacency matrix would waste a lot of space.
Both adjacency matrices and adjacency lists can be used in a program to make algo-
rithms more efficient. For example, it takes
O
(1) constant time to check whether two
vertices are connected using an adjacency matrix, and it takes linear time
O
(
m
) to print
all edges in a graph using adjacency lists, where
m
is the number of edges.
adjacency matrices vs.
adjacency lists
Search WWH ::
Custom Search