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

perform a breadth-first search. Depth-first search and breadth-first search will be introduced
in the next section. Figure 28.9 illustrates these methods in the UML diagram.
AbstractGraph does not introduce any new methods. A list of vertices and an edge adja-
cency list are defined in the AbstractGraph class. With these data fields, it is sufficient to

V

The generic type is the type for vertices.

«interface»
Graph<V>

+ getSize(): int
+ getVertices(): List<V>
+ getVertex(index: int): V
+ getIndex(v: V): int
+ getNeighbors(index: int): List<Integer>
+ getDegree(index: int): int
+ printEdges(): void
+ clear(): void
+ addVertex(v, V): boolean

Returns the number of vertices in the graph.
Returns the vertices in the graph.
Returns the vertex object for the specified vertex index.
Returns the index for the specified vertex.
Returns the neighbors of vertex with the specified index.
Returns the degree for a specified vertex index.
Prints the edges.
Clears the graph.
Returns true if v is added to the graph. Returns false if v
is already in the graph.
Adds an edge from u to v to the graph throws
IllegalArgumentException

+ addEdge(u: int, v: int): boolean

if u or v is invalid. Returns true
if the edge is added and false if (u, v) is already in the graph.
Obtains a depth-first search tree starting from v.
Obtains a breadth-first search tree starting from v.

+ dfs(v: int): AbstractGraph<V>.Tree
+ bfs(v: int): AbstractGraph<V>.Tree

AbstractGraph<V>

#vertices: List<V>
#neighbors: List<List<Edge>>

Vertices in the graph.
Neighbors for each vertex in the graph.

#AbstractGraph()
#AbstractGraph(vertices: V[], edges:
int[][])
#AbstractGraph(vertices: List<V>, edges:
List<Edge>)
#AbstractGraph(edges: int[][],
numberOfVertices: int)
#AbstractGraph(edges: List<Edge>,
numberOfVertices: int)
+addEdge(e: Edge): boolean
Inner classes Tree is defined here

Constructs an empty graph.
Constructs a graph with the specified edges and vertices
stored in arrays.
Constructs a graph with the specified edges and vertices
stored in lists.
Constructs a graph with the specified edges in an array
and the integer vertices 1, 2, ....
Constructs a graph with the specified edges in a list and
the integer vertices 1, 2, ….

Adds an edge into the adjacency edge list.

UnweightedGraph<V>

+UnweightedGraph()
+UnweightedGraph(vertices: V[], edges:
int[][])
+UnweightedGraph(vertices: List<V>,
edges: List<Edge>)
+UnweightedGraph(edges: List<Edge>,
numberOfVertices: int)
+UnweightedGraph(edges: int[][],
numberOfVertices: int)

Constructs an empty unweighted graph.
Constructs a graph with the specified edges and vertices
in arrays.
Constructs a graph with the specified edges and vertices
stored in lists.
Constructs a graph with the specified edges in an array
and the integer vertices 1, 2, ....
Constructs a graph with the specified edges in a list and
the integer vertices 1, 2, ….

F IGURE 28.9

The Graph interface defines the common operations for all types of graphs.