I'm trying to create a graph, and I'm a little confused on how to implement the vertices, edges, and their pointers. So, I'm following the adjacency-list model where it is similar to a hash table. The vertices are stored in an array and point to their edges that are stored in linked lists. Here is where I'm a little confused.
From my understanding, instead of a vertex pointing to the next vertex, it points to an edge, and this edge points to another vertex. If it is undirected, it also points back to the original vertex.
Now, the way it is stored in the hash table, the vertex points to an edge, which points to another edge, and so on, with no previous pointers.
Here is my code for the vertices and edges:
So, if i read in a new vertex. I create a new vertex with "new vertex". Then, when I read a new edge, i set "edge *next" to point to the new edge. When i create the edge, i set the target to the vertex it points to. If i read in another edge for that vertex, the previous edge's "nextEdge" points to the next edge. So, "int target" points to the vertex the edge is pointing to. Am i on the right track here? And, how do i differentiate between a directed edge and an undirected edge? I was thinking about adding an "int source" in to edge, and have source be Null if it is directed, and set it to the vertex number if it is undirected. This is probably the wrong way to do it. Or maybe i should be using pointers?Code:struct edge { edge() : weight(1) {}; int target; string label; int weight; edge *nextEdge; }; struct vertex { int id; string label; int edgeCount; edge *next; };
Any help is appreciated.
Thanks