Search
O(n)Insert
O(1) (constant time)Delete
O(e)Where n is the number of nodes and e is the number of edges
Finally, we have reached the pinnacle of abstract data structures, the graph! Graphs are also our first multidimensional data structure, as we now will be defining our Nodes with Collections of neighbors, instead of one or two instance variables.
According to Wikipedia:
In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges.
[...]
Vertices are also called nodes or points, and edges are also called arcs or lines.
This will also be the first data structure we work with that requires more than two files to run. We have our expected Node and Graph files, but we include a new class Edge to represent a connection between Nodes in the Graph. Edges also have a weight, or distance, between Nodes. Our Graph logic will have to handle both of these classes.
Graphs should have the following methods at minimum:
public void addNode(Node node) - Insert a new Node into the Graphpublic void addEdge(Edge edge) - Insert a new Edge into the Graphpublic String toString() - Convert the Graph into a String