A Practical Introduction to Data Structures and Algorithm Analysis Third Edition (Java Version)
Clifford A. Shaffer · 2010
class Graph has methods to return the number of vertices and edges (methods n and e, respectively). Function weight returns the weight of a given edge, with that edge identified by its two incident vertices. For example, calling weight(0, 4) on the graph of Figure 11.1 (c) would return 4. If no such edge exists, the weight is defined to be 0. So calling weight(0, 2) on the graph of Figure 11.1 (c) would return 0. Functions setEdge and delEdge set the weight of an edge and remove an edge from the graph, respectively. Again, an edge is identified by its two incident vertices. setEdge does not permit the user to set the weight to be 0, because this value is used to indicate a non-existent edge, nor are negative edge weights permitted. Functions getMark and setMark get and set, respectively, a requested value in the Mark array (described below) for Vertex V . Nearly every graph algorithm presented in this chapter will require visits to all neighbors of a given vertex. Two methods are provided to support this. They work in a manner similar to linked list access functions. Function first takes as input a vertex V , and returns the edge to the first neighbor for V (we assume the neighbor list is sorted by vertex number). Function next takes as input Vertices V1 and V2 and returns the index for the vertex forming the next edge with V1 after V2 on V1’s Sec. 11.2 Graph Implementations 407 // Graph abstract class. This ADT assumes that the number // of vertices is fixed when the graph is created. class Graph { private: void operator =(const Graph&) {} // Protect assignment Graph(const Graph&) {} // Protect copy constructor public: Graph() {} // Default constructor virtual Graph() {} // Base destructor // Return the number of vertices in the graph virtual int n() =0; // Return the current number of edges in the graph virtual int e() =0; // Store an edge from v1 to v2 with weight wgt virtual void setEdge(int v1, int v2, int wgt) =0; // Delete the edge going from v1 to v2 virtual void delEdge(int v1, int =0; // Return weight of the edge from v1 to v2. // Return 0 if no such edge exists. virtual int weight(int v1, int =0; // Get the mark value for vertex v virtual int getMark(int v) =0; // Set the mark value for vertex v to be val virtual void setMark(int v, int val) =0; // Return the index of the first neighbor for vertex v virtual int first(int v) =0; // Return the index of the next neighbor // (after v2) for vertex v1 virtual int next(int v1, int =0; }; Figure 11.5 A graph ADT. This ADT assumes that the number of vertices is fixed when the graph is created, but that edges can be added and removed. It also supports a mark array to aid graph traversal algorithms.