CareerCup

// Define a structure for graph node
struct Node
{
struct arch *first;
int info;
struct Node *next;
};

// Define a structure for graph edge
struct arch
{
struct Node *second;
struct arch *next; // next arch for the same node
};

class Graph
{
private:
struct Node *startNode;
public:
Graph():startNode(NULL){ }
struct Node *getNode();
struct arc *getArc();
void populateNode(struct Node *); // link node with the archs it is pointing too.
};

Please advise if this is correct.

struct GraphNode
{
void *data;
struct GraphNode* children;
}gNode;

class Graph
{
public:
Graph(gNode node):root(node){};
~Graph();
void insert(gNode node);
void delete(gNode node);
int totalNodes();
private:
gNode* root;
};

Node and arc are same as in vipin's solution
But I would define Graph differently

class Graph
{
private:
struct Node *startNode;
public:
Graph():startNode(NULL){ }
struct Node *addNode();
struct arc *addArc();
void traverseGraph();
void deleteNode();
void deleteArc();
void populateNode(struct Node *); // link node with the archs it is pointing too.
};

// custom data here....
struct node
{
int foo;
int bar;
// user friendly way to recognize a node
string nodeId;
}
class Graph
{
// create a preset graph
Graph(vector<node*> data, int[][] relationMatrix);
// create empty graph with no nodes....
Graph();
addNode(node* toAdd, vector<string> neighBours);
deleteNode(string id);
node* getNode(string id);
vectot<node*> getNeighBours();

int getNodeCount();
traverse(node* startNode);
// will start from first node added
traverse();
}

crap