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

neighbors[0] Seattle 1 3 5

neighbors[1] San Francisco 0 2 3

neighbors[2] Los Angeles 1 3 4 10

Denver

neighbors[3]
neighbors[4]

0 1 2 4 5

Kansas City 2 3 5 7 8 10

Chicago

neighbors[5]

0 3 4 6 7

neighbors[6] Boston 5 7

New York

neighbors[7]

4 5 6 8

neighbors[8] Atlanta 4 7 9 10 11

Miami

neighbors[9]

8 11

neighbors[10] Dallas 2 4 8 11

neighbors[11]

Houston 8 9 10

F IGURE 28.6

Edges in the graph in Figure 28.1 are represented using adjacency vertex lists.

neighbors[0]
neighbors[1]

Edge(0, 1) Edge(0, 3) Edge(0, 5)

Seattle

San Francisco Edge(1, 0) Edge(1, 2) Edge(1, 3)

neighbors[2]

Los Angeles Edge(2, 1) Edge(2, 3) Edge(2, 4) Edge(2, 10)

neighbors[3]
neighbors[4]

Denver Edge(3, 0) Edge(3, 1) Edge(3, 2) Edge(3, 4) Edge(3, 5)

Kansas City Edge(4, 2) Edge(4, 3) Edge(4, 5) Edge(4, 7) Edge(4, 8) Edge(4, 10)

neighbors[5] Chicago Edge(5, 0) Edge(5, 3) Edge(5, 4) Edge(5, 6) Edge(5, 7)

neighbors[6]
neighbors[7]

Boston Edge(6, 5) Edge(6, 7)

New York Edge(7, 4) Edge(7, 5) Edge(7, 6) Edge(7, 8)

neighbors[8] Atlanta Edge(8, 4) Edge(8, 7) Edge(8, 9) Edge(8, 10) Edge(8, 11)

neighbors[9]
neighbors[10]

Miami Edge(9, 8) Edge(9, 11)

Dallas Edge(10, 2) Edge(10, 4) Edge(10, 8) Edge(10, 11)

neighbors[11] Houston Edge(11, 8) Edge(11, 9) Edge(11, 10)

F IGURE 28.7

Edges in the graph in Figure 28.1 are represented using adjacency edge lists.

Note
Adjacency vertex list is simpler for representing unweighted graphs. However, adjacency
edge lists are more flexible for a wide range of graph applications. It is easy to add addi-
tional constraints on edges using adjacency edge lists. For this reason, this topic will use
adjacency edge lists to represent graphs.

adjacency vertex list vs.
adjacency edge lists

You can use arrays, array lists, or linked lists to store adjacency lists. We will use lists
instead of arrays, because the lists are easily expandable to enable you to add new vertices.
Further we will use array lists instead of linked lists, because our algorithms only require
searching for adjacent vertices in the list. Using array lists is more efficient for our algorithms.
Using array lists, the adjacency edge list in Figure 28.6 can be built as follows:

using ArrayList

List<ArrayList<Edge>> neighbors = new ArrayList<>();
neighbors.add( new ArrayList<Edge>());
neighbors.get( 0 ).add( new Edge( 0 , 1 ));