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

Now we turn our attention to implementing the interface and classes. Listings 28.2, 28.3,
and 28.4 give the Graph interface, the AbstractGraph class, and the UnweightedGraph
class, respectively.

L ISTING 28.2

Graph.java
1 public interface Graph<V> {
2 /** Return the number of vertices in the graph */

3 public int getSize();

getSize

4
5

/** Return the vertices in the graph */

6 public java.util.List<V> getVertices();

getVertices

7
8 /** Return the object for the specified vertex index */

9 public V getVertex( int index);

getVertex

10
11

/** Return the index for the specified vertex object */

12 public int getIndex(V v);

getIndex

13
14 /** Return the neighbors of vertex with the specified index */

15 public java.util.List<Integer> getNeighbors( int index);

getNeighbors

16
17 /** Return the degree for a specified vertex */

18 public int getDegree( int v);

getDegree

19
20

/** Print the edges */

21 public void printEdges();

printEdges

22
23 /** Clear the graph */

24 public void clear();

clear

25
26

/** Add a vertex to the graph */

27 public void addVertex(V vertex);

addVertex

28
29 /** Add an edge to the graph */

30 public void addEdge( int u, int v);

addEdge

31
32

/** Obtain a depth-first search tree starting from v */

33 public AbstractGraph<V>.Tree dfs( int v);

dfs

34
35 /** Obtain a breadth-first search tree starting from v */

36 public AbstractGraph<V>.Tree bfs( int v);

bfs

37 }

L ISTING 28.3

AbstractGraph.java
1 import java.util.*;
2
3 public abstract class AbstractGraph<V> implements Graph<V> {
4 protected List<V> vertices = new ArrayList<>(); // Store vertices
5 protected List<List<Edge>> neighbors
6 = new ArrayList<>(); // Adjacency lists
7
8 /** Construct an empty graph */
9 protected AbstractGraph() {
10 }
11
12

no-arg constructor

/** Construct a graph from vertices and edges stored in arrays */

13 protected AbstractGraph(V[] vertices, int [][] edges) { constructor