// 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
// Initialize a graph of n vertices
virtual void Init(int n) =0;
// Return: the number of vertices and edges
virtual int n() =0;
virtual int e() =0;
// Return v’s first neighbor
virtual int first(int v) =0;
// Return v’s next neighbor
virtual int next(int v, int w) =0;
// Set the weight for an edge
// i, j: The vertices
// wgt: Edge weight
virtual void setEdge(int v1, int v2, int wght) =0;
// Delete an edge
// i, j: The vertices
virtual void delEdge(int v1, int v2) =0;
// Determine if an edge is in the graph
// i, j: The vertices
// Return: true if edge i,j has non-zero weight
virtual bool isEdge(int i, int j) =0;
// Return an edge’s weight
// i, j: The vertices
// Return: The weight of edge i,j, or zero
virtual int weight(int v1, int v2) =0;
// Get and Set the mark value for a vertex
// v: The vertex
// val: The value to set
virtual int getMark(int v) =0;
virtual void setMark(int v, int val) =0;
};

// Edge class for Adjacency List graph representation
class Edge {
int vert, wt;
public:
Edge() { vert = -1; wt = -1; }
Edge(int v, int w) { vert = v; wt = w; }
int vertex() { return vert; }
int weight() { return wt; }
};

// Implementation for the adjacency matrix representation
class Graphm : public Graph {
private:
int numVertex, numEdge; // Store number of vertices, edges
int **matrix; // Pointer to adjacency matrix
int *mark; // Pointer to mark array
public:
Graphm(int numVert) // Constructor
{ Init(numVert); }
˜Graphm() { // Destructor
delete [] mark; // Return dynamically allocated memory
for (int i=0; i<numVertex; i++)
delete [] matrix[i];
delete [] matrix;
}
void Init(int n) { // Initialize the graph
int i;
numVertex = n;
numEdge = 0;
mark = new int[n]; // Initialize mark array
for (i=0; i<numVertex; i++)
mark[i] = UNVISITED;
matrix = (int**) new int*[numVertex]; // Make matrix
for (i=0; i<numVertex; i++)
matrix[i] = new int[numVertex];
for (i=0; i< numVertex; i++) // Initialize to 0 weights
for (int j=0; j<numVertex; j++)
matrix[i][j] = 0;
}
int n() { return numVertex; } // Number of vertices
int e() { return numEdge; } // Number of edges
// Return first neighbor of "v"
int first(int v) {
for (int i=0; i<numVertex; i++)
if (matrix[v][i] != 0) return i;
return numVertex; // Return n if none
}
// Return v’s next neighbor after w
int next(int v, int w) {
for(int i=w+1; i<numVertex; i++)
if (matrix[v][i] != 0)
return i;
return numVertex; // Return n if none
}
Figure 11.6 An implementation for the adjacency matrix implementation.
390 Chap. 11 Graphs
// Set edge (v1, v2) to "wt"
void setEdge(int v1, int v2, int wt) {
Assert(wt>0, "Illegal weight value");
if (matrix[v1][v2] == 0) numEdge++;
matrix[v1][v2] = wt;
}
void delEdge(int v1, int v2) { // Delete edge (v1, v2)
if (matrix[v1][v2] != 0) numEdge--;
matrix[v1][v2] = 0;
}
bool isEdge(int i, int j) // Is (i, j) an edge?
{ return matrix[i][j] != 0; }
int weight(int v1, int v2) { return matrix[v1][v2]; }
int getMark(int v) { return mark[v]; }
void setMark(int v, int val) { mark[v] = val; }
};

void graphTraverse(Graph* G) {
int v;
for (v=0; v<G->n(); v++)
G->setMark(v, UNVISITED); // Initialize mark bits
for (v=0; v<G->n(); v++)
if (G->getMark(v) == UNVISITED)
	doTraverse(G, v);
}

void DFS(Graph* G, int v) { // Depth first search
PreVisit(G, v); // Take appropriate action
G->setMark(v, VISITED);
for (int w=G->first(v); w<G->n(); w = G->next(v,w))
	if (G->getMark(w) == UNVISITED)
		DFS(G, w);
PostVisit(G, v); // Take appropriate action
}