WEIGHTED GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1063

F IGURE 29.2

You can use the tool to create a weighted graph with mouse gestures and show the MST and shortest paths.

29.2 Representing Weighted Graphs
Weighted edges can be stored in adjacency lists.

Key
Point
vertex-weighted graph
edge-weighted graph

There are two types of weighted graphs: vertex weighted and edge weighted. In a vertex-
weighted graph , each vertex is assigned a weight. In an edge-weighted graph , each edge
is assigned a weight. Of the two types, edge-weighted graphs have more applications. This
chapter considers edge-weighted graphs.
Weighted graphs can be represented in the same way as unweighted graphs, except that
you have to represent the weights on the edges. As with unweighted graphs, the vertices in
weighted graphs can be stored in an array. This section introduces three representations for
the edges in weighted graphs.

29.2.1 Representing Weighted Edges: Edge Array
Weighted edges can be represented using a two-dimensional array. For example, you can
store all the edges in the graph in Figure 29.3a using the array in Figure 29.3b.

Note
Weights can be of any type: Integer , Double , BigDecimal , and so on. You
can use a two-dimensional array of the Object type to represent weighted edges as
follows:

Object[][] edges = {
{ new Integer( 0 ), new Integer( 1 ), new SomeTypeForWeight( 2 )},
{ new Integer( 0 ), new Integer( 3 ), new SomeTypeForWeight( 8 )},
...
};