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

neighbors.get( 0 ).add( new Edge( 0 , 3 ));
neighbors.get( 0 ).add( new Edge( 0 , 5 ));
neighbors.add( new ArrayList<Edge>());
neighbors.get( 1 ).add( new Edge( 1 , 0 ));
neighbors.get( 1 ).add( new Edge( 1 , 2 ));
neighbors.get( 1 ).add( new Edge( 1 , 3 ));
...
...
neighbors.get( 11 ).add( new Edge( 11 , 8 ));
neighbors.get( 11 ).add( new Edge( 11 , 9 ));
neighbors.get( 11 ).add( new Edge( 11 , 10 ));

28.5

✓ ✓

How do you represent vertices in a graph? How do you represent edges using an edge
array? How do you represent an edge using an edge object? How do you represent
edges using an adjacency matrix? How do you represent edges using adjacency lists?

Check

Point

28.6

Represent the following graph using an edge array, a list of edge objects, an adja-
cency matrix, an adjacency vertex list, and an adjacency edge list, respectively.

1

4

0 3

2 5

28.4 Modeling Graphs
The Graph interface defines the common operations for a graph.

Key
Point

The Java Collections Framework serves as a good example for designing complex data struc-
tures. The common features of data structures are defined in the interfaces (e.g., Collection ,
Set , List , Queue ), as shown in Figure 20.1. Abstract classes (e.g., AbstractCollection ,
AbstractSet , AbstractList ) partially implement the interfaces. Concrete classes (e.g.,
HashSet , LinkedHashSet , TreeSet , ArrayList , LinkedList , PriorityQueue ) provide
concrete implementations. This design pattern is useful for modeling graphs. We will define an
interface named Graph that contains all the common operations of graphs and an abstract class
named AbstractGraph that partially implements the Graph interface. Many concrete graphs can
be added to the design. For example, we will define such graphs named UnweightedGraph and
WeightedGraph . The relationships of these interfaces and classes are illustrated in Figure 28.8.

UnweightedGraph

Graph AbstractGraph

WeightedGraph

Interface Abstract Class Concrete Classes

F IGURE 28.8

Graphs can be modeled using interfaces, abstract classes, and concrete classes.

What are the common operations for a graph? In general, you need to get the number of
vertices in a graph, get all vertices in a graph, get the vertex object with a specified index, get
the index of the vertex with a specified name, get the neighbors for a vertex, get the degree for
a vertex, clear the graph, add a new vertex, add a new edge, perform a depth-first search, and