There are two main ways of representing graphs in computer memory. For simplicity, we will only consider simple graphs (i.e. no multi-graphs or self-loops).
Adjacency Matrix
The first method of storing graphs is through the means of an adjacency matrix. This simply means we have an V * V matrix where each cell contains a 0 if there is no edge running from one vertex to another, otherwise we will have either a 1 or a positive value (for weighted graphs). So for example, if we had a graph that had an edge from vertex 2 to vertex 5, then the cell of [2,5] would contain a 1. If the edge was weighted with say 3, we would mark the cell of [2,5] with 3. Note that this notation supports both undirected and directed graphs. Note that for particularly sparse graphs, there is a considerable amount of wasted space (O( | V | 2)). So an adjacency matrix isn't practical for sparse or large graphs in general since the space requirements grow quadratically. However, what we gain from this representation is speed and simplicity when determining whether there is an edge going from vertex n to vertex m since we just merely have to lookup the appropriate cells (a constant time operation). See also Adjacency Matrix for a neat algebraic property of this data structure.
For implementation, let's write some basic code to convert edges and place them into a simplistic adjacency matrix. For our purposes, let's assume the graph is weighted and directed, and the input comes in form of a string vector/array, each string contains three elements ("A B W"), which means there is an edge going from A to B with a weight of W (where A,B < NUM_EDGES). After we have inserted the edges into the graph representation, we will print out all the adjacent vertices with their corresponding weights.
#define NUM_EDGES 10
int adjmat[NUM_EDGES][NUM_EDGES];
memset(adjmat,0,sizeof(adjmat)); // default: no connectivity
for (int i = 0; i < input.size(); i++ ) {
istringstream iss(input[i]);
int A, B, W; iss >> A >> B >> W; // parse each input into the three integers
adjmat[A][B] = W;
}
for (int i = 0; i < NUM_EDGES; i++ ) {
for (int j = 0; j < NUM_EDGES; j++ ) {
if (adjmat[i][j] > 0) {
cout << "There is an edge going from " << i << " to " << j << " with a weight of " << adjmat[i][j] << endl;
}
}
}Adjacency List
The second method of storing graphs is through a similar means to an adjacency matrix, but is more space efficient. This data structure is called an adjacency list. An adjacency list basically has V linked lists, with each corresponding linked list containing the elements that are adjacent to a particular vertex. So given the example we used earlier, we would have a linked list in cell 2 that contains a single element of 5. If vertex 2 was also adjacent to vertex 6 then the linked list in cell 2 would contain two elements, 5 and 6 and so forth. The space requirements grow in proportion to the number of edges plus the number of vertices, i.e. O( | V | + | E | ). If the graph was weighted, then we would need to create an abstraction of each node of the linked list. Instead of merely having a numerical value representing which vertices it was adjacent to, each node needs to have another field containing the weight of the edge.
Using the same restrictions and objectives as the adjacency matrix implementation, the adjacency list implementation follows:
#define NUM_EDGES 10
struct node {
int vertex;
int weight;
node(int v, int w) : vertex(v), weight(w) { }
node() { }
};
list<node> adjlist[NUM_EDGES];
for (int i = 0; i < input.size(); i++ ) {
istringstream iss(input[i]);
int A, B, W; iss >> A >> B >> W; // parse each input into the three integers
adjlist[A].push_back(node(B,W));
}
for (int i = 0; i < NUM_EDGES; i++ ) {
for (list<node>::iterator it = adjlist[i].begin(); it != adjlist[i].end(); ++it ) {
// note you don't need to check whether it's connected or not - adjacency list only
// represents edges which are present
cout << "There is an edge going from " << i << " to " << it->vertex;
cout << " with a weight of " << it->weight << endl;
}
}Incidence List
This structure is more flexible than adjacency list, but requires little more source code to implement it, and to use it. Each vertex has list of pointers to edges to which it is incident. Advantage of this is that two vertices that are adjacent to this edge share the same instance of edge, so when you want to manipulate with edge data, for example flow or cost, you only change data in one object. You also modify neighbor function to make your graph directed, or mixed. Imagine how easy it would be to change the orientation of the edge with this data structure.
struct edge{
int x,y,data;
edge (int xx,int yy,int d) :x(xx),y(yy), data(dd){}
int neighbour(int aa);
}
edge::neighbour(int aa) {
if(aa==x) return y;
return x;
}
vector<vector<edge*> > graph;
void addedge(int a,int b, int data) {
edge *tmp=new edge(a,b,data);
graph[a].push_back(tmp);
graph[b].push_back(tmp);
}