C++ Program

You will need to implement a templated Graph class that implements a graph whose nodes are of T . You will

need to implement this in two ways: using an adjacency list and adjacency matrix as your private implementation.

This means that you have to implement the Graph as an pure virtual abstract class (if youre using C++). Use

different sub-classes of the Graph class for implementing the adjacency list and adjacency matrix representations

of a Graph .

NOTE : This means you have to implement three classes: the abstract base classs and two sub-classes that

implement the different data structures!

The Graph will need to implement provide the following interface:

bool adjacent(T x, T y) : Is there a path from x to y ?

vector neighbors(T x) : Return a vector containing the nodes that have a edge from x to elements

in the vector.

void addEdge(T x, T y) : Add an edge from x to y if none exists. The node x must exist in the graph and

you need to add the node y to the graph if it does not exist.

void deleteEdge(T x, T y) : Delete the edge from x to y if one exists. Your method needs to address the

special case of what happens if deleting the edge disconnects (directly or indirectly) the node y from the rest

of the graph.

1

void deleteNode(T x) : Delete the node x from the graph. Make certain that you do not leave any dangling

edges from other nodes to the newly deleted node.

void dfs(Graph &g, T &startNode) : Do a depth-first traversal of the graph g , starting from node

startNode . You may either print the contents of each node or implement the extra credit portion of the

assignment.

void bfs(Graph &g, T &startNode) : Do breath-first traversal of the graph g , starting from node

startNode .

Use the program you just created to guess the performance of the depth first search of a graph represented

in an adjacency matrix. Generate graphs with sizes of 2, 8, 64, 256, and 1024 nodes, each with a random

number of edges, with edge probability of 0.5. Report how long (in seconds) it takes for your program to

execute the search.