Hi this is my first time to the forums and I am hoping to recieve some help on a project I am working on.

I am trying to create an undirected graph using adjacency lists
I have my class that creates the links between vertices, and i have a struct that contains
struct Node
{
int vertex;
Node * next;
}

Node *Headnodes;
HeadNodes = new Node[X];

How can I go through each and be able to add to each subscripted array and go through the list
so if the user enters (1,0), (2,0) (3,2);
then
HeadNode[0] = 0-->1-->2
HeadNode[1] = 1-->0
HeadNode[2] = 2-->0-->3
HeadNode[3] = 3-->2

The code I use, is what would be used in a regular stack code and it gives me answers like
HeadNode[0] = 1-->1-->1-->1-->....(forever)
HeadNode[1] = 0-->0-->0-->0-->....(forever)
i stepped through the code and can't figure out why its doing it that way at all

void CGraph::CCreate(int xLoc, int yLoc)
{
node *yPtr;
node *xPtr;

node *Xtemp;
node *Ytemp;

xPtr = new node;
yPtr = new node;

xPtr = &HeadNodes[xLoc];
yPtr = &HeadNodes[yLoc];

Xtemp = new node;
Ytemp = new node;

Xtemp->vertex = xLoc;
Xtemp->next = yPtr;
yPtr = Xtemp;
HeadNodes[yLoc] = *yPtr; //This is where it erases both the *yPtr and the HeadNodes[yLoc] to a forever list

Ytemp->vertex = yLoc;
Ytemp->next = xPtr;
xPtr = Ytemp;
HeadNodes[xLoc] = *xPtr; //Same problem here
}

Any help would be greatly appreciated, thank you so much in advance for the help.

You need to have two separate sets of lists: the list of the vertices, and a list which might or might not exist representing the various out edges from a particular vertex. So - have two node pointers - vNode and eNode - and you should be covered [all of the eNode[s] will have vNode = null].

No ... each node would have two Node* pointers - one being vNode and the other being eNode

in your example, the nodes would be linked 0-1-2-3 by their vNode pointers

then you would have a list from the "0" node with eNode pointers going to 1 to 2
from the 1 node pointing to 0
from the 2 node pointing to 0 and 3
from the 3 node pointing to 2

you can make the "vNode" list be a backbone, then have a linked list of Nodes "coming off" the back bone at each level ...

So is there no way to just use one Node Array?
Its not as simple as
headnode[0] = 0->1->3
HeadNode[1] = 1->0
HeadNode[2] = 2
HeadNode[3] = 3->0
?
i can't just make it that each index is its own linked list
as if i'd be making a Stack?

You asked about the classic structure of the adjacency lists representation of a graph.

Sure, I don't know why you cannot have the various "edge" lists come off array backing. There is no magic on the "list" being "linked" or "indexed in an array".

You might also decide to have a collection of pointers stored for "nextNode" - 0-1, 0-2 - stored in a vector which is part of your node struc or class.

So yes, you have the freedom to do this. It might work for you. Do some research into the functionality you will have to create to make your structure do what you want.

Don't sell the two "nodeTypes" idea short, however, and the power of having real information being stored in these nodes. In the "real world" graphs are used to represent MANY real relationships - Sudoku challenges, maps, schedules, people, all sorts of things which have relationships. Vertex nodes will store very different information from that stored in Edge nodes. Vertex nodes will hold location information - how hot it is, elevation, restaurants available, classrooms at the location, class description and prerequisites and current enrollment, etc. Edges nodes will hold "weight" information - distance, time, difficulty, scenery - and this information will be very different for a trip from 0-1 than for 2-1. Where does your structure provide a place for that different information? How do you propose to have a node located at 0 in your array hold its "location" data as well as the "weight" data for each of the trips to the nodes it is adjacent to?

Well for now I am not going to worry about the edge idea, as far as the weight of the graph between each vertex.

I just want to be able to show each node and what they would be connected to.
So that is why I don't get why I need to have two Nodes, is there maybe a site that may explain how it all works and can anyone tell me why I can't just have an Array of linked lists...

Maybe explaining it in some other way b/c I just don't get it.

Thanks for your time again, I really appreciate this!

What you wrote is certainly do-able, Peter. You provide a storage structure which holds your representation of the vertices (nodes) of the graph. Each vertex can have a storage structure which holds a representation (be it a struct or a class object) of the "edges" which originate (are outbound) from that vertex.

I found another reference which is a good one page summary of graph theory.

One of the data members of your "edge" class could be the weight of that edge. You might also store the two vertices connected by that edge, but that's up to you. If the graph is undirected, I suggest having two edge objects for each edge of the graph - so each edge represents one direction of traversal in the graph.

You asked:

"What is edge-list representation ? what is the advantages of this representation compare to array of pointers ?"

You can use arrays of pointers for your work in your program. However, you need to have data which is being pointed to by those pointers. The object you choose to use as the representation of each vertex and the object you choose to use as the representation of each edge are the data which can be pointed to by your pointers.

The two main representations of a graph usually used in graph theory are adjacency list/edge-list and matrix. You can use pointers in either representation.