Java Reference
In-Depth Information
vertex
weight
int
[][] edges = {{
0
,
1
,
2
}, {
0
,
3
,
8
},
{
1
,
0
,
2
}, {
1
,
2
,
7
}, {
1
,
3
,
3
},
{
2
,
1
,
7
}, {
2
,
3
,
4
}, {
2
,
4
,
5
},
{
3
,
0
,
8
}, {
3
,
1
,
3
}, {
3
,
2
,
4
}, {
3
,
4
,
6
},
{
4
,
2
,
5
}, {
4
,
3
,
6
}
7
1
2
3
4
5
2
8
6
0
3
4
};
(a)
(b)
F
IGURE
29.3
Each edge is assigned a weight in an edge-weighted graph.
29.2.2 Weighted Adjacency Matrices
Assume that the graph has
n
vertices. You can use a two-dimensional
n
n
matrix, say
weights
, to represent the weights on edges.
weights[i][j]
represents the weight on
edge (
i
,
j
). If vertices
i
and
j
are not connected,
weights[i][j]
is
null
. For example,
the weights in the graph in Figure 29.3a can be represented using an adjacency matrix as
follows:
*
Integer[][] adjacencyMatrix = {
{
null
,
2
,
null
,
8
,
null
},
{
2
,
null
,
7
,
3
,
null
},
{
null
,
7
,
null
,
4
,
5
},
{
8
,
3
,
4
,
null
,
6
},
{
null
,
null
,
5
,
6
,
null
}
};
0
1
2
3
4
0 null 2
null
8
null
1 2
null 7
3
null
2 null 7
null
4
5
3 8
3
4
null 6
4 null null 5
6
null
29.2.3 Adjacency Lists
Another way to represent the edges is to define edges as objects. The
AbstractGraph.Edge
class was defined to represent an unweighted edge in Listing 28.3. For weighted edges, we
define the
WeightedEdge
class as shown in Listing 29.1.
L
ISTING
29.1
WeightedEdge.java
1
public class
WeightedEdge
extends
AbstractGraph.Edge
2
implements
Comparable<WeightedEdge> {
3
public double
weight;
// The weight on edge (u, v)
edge weight
4
5
/** Create a weighted edge on (u, v) */
6
public
WeightedEdge(
int
u,
int
v,
double
weight) {
constructor
7
super
(u, v);
8
this
.weight = weight;
9 }
10
11 @Override
/** Compare two edges on weights */
12
public int
compareTo(WeightedEdge edge) {
compare edges
13
if
(weight > edge.weight)
14
return
1
;
15
else if
(weight == edge.weight)
16
return
0
;
17
else
18
return
-1
;
19 }
20 }
Search WWH ::
Custom Search