|
Well you give a rather broad question. Exactly how you would want to represent a graph in memory really is up to you as there are LOTS of ways to do it. The basic way mimics how mathematics might store a graph in a matrix. There are however a few ways that mathematicians do that.
On way is to make each column and row represent a vertex. For a graph with 4 verticies this results in a 4x4 matrix, and therefore a 4 x 4 array. The element Array[row][col] tells you if there is an edge connecting those two. The nice thing about this is that you can represent directed graphs. For example if Array[1][2] = 1 but Array[2][1] = 0 then we know that there is a path from 1 to 2 but not a path from 2 to 1.
...1 2 3 4
...-------
1| 0 1 1 0
2| 1 0 0 1
3| 1 0 0 0
4| 0 1 0 0
This method has its advantages, it also has its disadvantages. It wastes space for many types of graphs, it is not all that easy to add in verticies (you have to create a new array, and then copy over that data.) BUT we can also represent directed graphs, weighted graphs, colored graphs etc etc etc using this method.
Another method of representing a graph is an array of 2D values. X and Y would be verticies and the pair represents an edge. This again has its ups and its downs. For example listing all of the verticies requires you to search the entire array looking for them. This is why there generally is also another array containing the possible verticies. (This seems to be what you teacher is asking for....)
Another method of storing graphs is to use a graph data structure (but your teacher seems to want to you use vectors). This is much like a multi-linked linked list.
If your requirements are just to add/delete vertecies, add/edit/delete edges, and find paths that either of the two examples I gave will work. The second one might be easier to impliment.
|
| 