C++: is a Graph ADT supposed to have a list of vertices and a list of edges or just vertices with pointers to other vertices?

Question

I'm trying to implement a graph in C++, I'm not sure if there is a 'proper' way of going about this. should each of my vertices contain a list of vertices it points to, or should the graph object contain a list of vertices and a list of edges.

Answer 1

This depends on what type of graph you are dealing with, If your graph is weighted, you can't just have a list of pointers because you won't be able to assign a weight for this connection. In this case I would suggest that every node will contain a list of edges that are connected to it. if the graph is not directed, then for any vertices i and j you can save a pointer to the same edge {i, j}, if it is directed then edge {i, j} and {j, i} are two different object.

Another approach is to save an NxN matrix that represents the connections between all the vertices. if the graph is not weighted, then each cell [i, j] will have 1 if a edge exists between vertex i to vertex j. if the graph is weighted then cell [i, j] will contain the distance between vertex i to vertex j, and infinity or -1 if the edges doesn't exist.

If your graph is complete (every vertex is connected to all the other vertices), I strongly recommend using the matrix technique, as it is very easy to implement, gives you direct access to any relevant value, and doesn't take extra memory or running time (for example, when you want to iterate through all the edges connected to a certain vertex), as any vertex will contain a list of connections to all the other vertices anyway.

Answer 2

It depends on your access the graph data. You can define two dimentional vector as follows:

vector< vector<int> > nodes;

where nodes ids are 0 to number_of_nodes -1; node 6 would be stored in nodes[6], and son on.