I'm trying to figure out an efficient way of implementing a graph, and I'm not sure how to go about it. More specifically, say I have five members (vertices) whose edges are as follows:
I have a structure of nodes to hold the information about each vertex, and a vector of node* with one entry for each vertex:
A - B
B - D
C - B
E - C
E - A
I also have a function to add a new vertex if it doesn't already exist, and return a pointer to the new node. My problem is that I can not, for the life of me, figure out a way to split the vertices into two groups. With pen and paper, I know that the groups are:
vector<node *> links;
vector<node *> vertex;
Something is telling me I might want to use a doubly-linked list in there somewhere, but I am sitting here scratching my head trying to figure this out. Any help would be much appreciated. Thank you.
Group 0: A, C, D
Group 1: B, E
You might want to look into the Adjacency List storage model. Are you using this to implement pathfinding of some sort?