The graph data structure

Before we begin, we need to detail a few characteristics that our graph structure will possess. Our graph will support nodes that have no edges to or from other nodes. Our graph will also support exclusive and bidirectional edges. For the sake of brevity, the edges in our graph collection will not support edge values, but adding values to edges is a simple matter if you decide to use them in your custom implementations.

Our graph will be made up of two classes. The first is the Graph class itself, which in our implementation will contain most of the standard graph operations. The next is a GraphNode class, which will represent the nodes of our collection. Note that this class could also be named GraphVertex or GraphPoint, but in keeping with our tree Node class example from Chapter 9, Trees: Non-linear Structures, we will stick with nodes.

The Graph class will be based on an array or list that contains the root references to the nodes. Each GraphNode object will...