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

when inserting an edge, we do not check whether it is already present. That
cannot be done in constant time (using a simple linked list), and doing the
check would destroy the linear-time bound for construction. In most cases,
ignoring this check is unimportant. If there are two or more edges of differ-
ent cost connecting a pair of vertices, any shortest-path algorithm will
choose the lower cost edge without resorting to any special processing. Note
also that ArrayList s can be used instead of linked lists, with the constant-
time add operation replacing insertions at the front.

In most real-life applications the vertices have names, which are unknown at
compile time, instead of numbers. Consequently, we must provide a way to
transform names to numbers. The easiest way to do so is to provide a map by
which we map a vertex name to an internal number ranging from 0 to
(the number of vertices is determined as the program runs). The internal numbers
are assigned as the graph is read. The first number assigned is 0. As each edge is
input, we check whether each of the two vertices has been assigned a number, by
looking in the map. If it has been assigned an internal number, we use it. Other-
wise, we assign to the vertex the next available number and insert the vertex
name and number in the map. With this transformation, all the graph algorithms
use only the internal numbers. Eventually, we have to output the real vertex
names, not the internal numbers, so for each internal number we must also
record the corresponding vertex name. One way to do so is to keep a string for
each vertex. We use this technique to implement a Graph class. The class and the
shortest-path algorithms require several data structures—namely, a list, a queue,
a map, and a priority queue. The import directives are shown in Figure 14.3. The
queue (implemented with a linked list) and priority queue are used in various
shortest-path calculations. The adjacency list is represented with LinkedList . A
HashMap is also used to represent the graph.

A map can be used
to map vertex
names to internal
numbers.

V - 1

1 import java.io.FileReader;
2 import java.io.InputStreamReader;
3 import java.io.BufferedReader;
4 import java.io.IOException;
5 import java.util.StringTokenizer;
6
7 import java.util.Collection;
8 import java.util.List;
9 import java.util.LinkedList;
10 import java.util.Map;
11 import java.util.HashMap;
12 import java.util.Iterator;
13 import java.util.Queue;
14 import java.util.PriorityQueue;
15 import java.util.NoSuchElementException;

figure 14.3
The import directives
for the Graph class