Representing Weighted Graphs

Weighted edges can be stored in adjacency lists.

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.

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 below (a) using the array in Figure below (b).

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)},
...
};

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 above (a) can be represented using an adjacency matrix as follows:

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 AbstractGraph.java. For weighted edges, we define the WeightedEdge class as shown in code below.

AbstractGraph.Edge is an inner class defined in the AbstractGraph class. It represents an edge from vertex u to v. WeightedEdge extends AbstractGraph.Edge with a new property weight.

To create a WeightedEdge object, use new WeightedEdge(i, j, w), where w is the weight on edge (i, j). Often you need to compare the weights of the edges. For this reason, the WeightedEdge class implements the Comparable interface.

For unweighted graphs, we use adjacency lists to represent edges. For weighted graphs, we still use adjacency lists, the adjacency lists for the vertices in the graph in Figure below a can be represented as follows:

java.util.List<WeightedEdge>[] list = new java.util.List[5];

list[i] stores all edges adjacent to vertex i.

For flexibility, we will use an array list rather than a fixed-sized array to represent list as follows:

List<List<WeightedEdge>> list = new java.util.ArrayList<>();