Graphs and paths - Data Structures and Problem Solving Using Java - page 532

When we write an actual Java implementation, we do not need internal
vertex numbers. Instead, each vertex is stored in a Vertex object, and instead
of using a number, we can use a reference to the Vertex object as its (uniquely
identifying) number. However, when describing the algorithms, assuming that
vertices are numbered is often convenient, and we occasionally do so.
Before we show the Graph class skeleton, let us examine Figures 14.4 and
14.5, which show how our graph is to be represented. Figure 14.4 shows the
representation in which we use internal numbers. Figure 14.5 replaces the
internal numbers with Vertex variables, as we do in our code. Although this
simplifies the code, it greatly complicates the picture. Because the two figures
represent identical inputs, Figure 14.4 can be used to follow the complications
in Figure 14.5.
As indicated in the part labeled Input , we can expect the user to provide a
list of edges, one per line. At the start of the algorithm, we do not know the
names of any of the vertices, how many vertices there are, or how many edges
there are. We use two basic data structures to represent the graph. As we men-
tioned in the preceding paragraph, for each vertex we maintain a Vertex object
that stores some information. We describe the details of Vertex (in particular,
how different Vertex objects interact with each other) last.
As mentioned earlier, the first major data structure is a map that allows us
to find, for any vertex name, the Vertex object that represents it. This map is
shown in Figure 14.5 as vertexMap (Figure 14.4 maps the name to an int in the
component labeled Dictionary ).

figure 14.4
An abstract scenario
of the data structures
used in a shortest-
path calculation, with
an input graph taken
from a file. The
shortest weighted
path from A to C is A to
B to E to D to C (cost is
76).

dist prev name adj

D C
A B
D B
A D
E D
B E
C A

10
12
23
87
43
11
19

0
1
2
3
4

66
76
0
12
23

4
0
-1
2
3

D
C
A
B
E

3 (23), 1 (10)
2 (19)
0 (87), 3 (12)
4 (11)
0 (43)

Input Graph table

12

A B

D (0)
B (3)

E (4)

11

87

19

23

C (1)

A (2)

D E

C

10 43

Visual representation of graph Dictionary