Section 10.3 The Graph Abstract Data Type
The graph abstract data type is defined as a collection of vertices and edges. Vertices may be either connected to each other or isolated. Edges join two vertices and may be weighted. Here is a Kotlin interface representing the ADT.
interface GraphADT<T> {
// Returns true if vertex added,
// false if not (because it was already there)
fun addVertex(id: T): Boolean
// Adds edge if not previously present;
// replaces weight with new one if edge already there.
// A default weight of 0 is placed if the function
// is called without specifying a weight.
fun addEdge(begin: T, end: T, weight: Double = 0.0)
// Returns true if vertex is present, false if not
fun containsVertex(id: T): Boolean
// Returns true if edge is present, false if not
fun containsEdge(begin: T, end: T): Boolean
// Returns a set of all vertex keys in the graph
fun getVertices(): Set<T>
// Returns a set of all neighbors to a vertex.
// Returns null if the vertex is not in the graph.
fun getNeighbors(id: T): Set<T>?
// Returns a map of all neighbors to a vertex,
// and the weights of the edges.
// Returns null if the vertex is not in the graph.
fun getNeighborsAndWeights(id: T): Map<T, Double>?
}
This ADT is for a weighted graph. To keep things simple, we have not created a second ADT for an unweighted graph, though we could have. Instead, we’ll just use this ADT for either case. If we wish to use this ADT for an unweighted graph, we’ll just use
addEdge and not specify a weight. Line 10 in the definition above puts in a default weight of zero, which we can ignore. Likewise, if we want to retrieve all neighbors for a particular vertex without concern about weights, we can use the getNeighbors method. Therefore, we can use this ADT for an unweighted graph by simply ignoring the weights.
Now that we have looked at the definition for the graph ADT, there are several ways we can implement it in Java. We will see that there are trade-offs in using different representations to implement the ADT described above. There are two well-known implementations of a graph, the adjacency matrix and the adjacency list. We will explain both of these options, and then implement one in Kotlin.
You have attempted of activities on this page.
