Graph Storage

Graph theory is of central importance in computer science. Many important problems reduce to solving a well known problem on general graphs. It is thus incredibly important to be able to store graphs in ways that facilitate the use of our handy algorithms.

To store a graph we must capture two pieces of information:

1. what are the graph vertices
2. how are the vertices connected (what are the graph edges)

Adjacency Matrix

One simple way to facilitate this is to store a VxV matrix (where V is the number of vertices). In this scheme the entry at [a][b] stores either a 1 or 0 to indicated that the vertices a and b are either connected or disconnected. In a weighted graph this entry can store the edge weight between the two vertices. It should be noted that in a graph with bi-directional edges the matrix will be symmetric about the diagonal.

Advantages:

• Checking to see if any two vertices are connected is O(1)

Disadvantages:

• It always requires $V^2$ space even when there are far fewer edges
• Finding all the neighbors of a node requires looping through all vertices

Adjacency List

Another storage method is to keep an array of dynamic arrays. In this scheme each dynamic array holds only the edges that are attached to a particular vertex.

Advantages:

• Finding all the neighbors of a vertex is much faster
• storage space is proportional to the number of edges

Disadvantages:

• Checking to see if any two vertices are connected requires looping through the dynamic array

Edge List

This is perhaps one of the most obvious possibilities, but is not often useful. One simply stores an array for all of the edges. The array contains the vertices connected and the length of each edge.

Advantages:

• O(E) storage is small for graphs with few edges
• Iterating through the edges is fast

Disadvantages:

• Finding the neighbors of a vertex is slow

Adj. Matrix

This creates a graph with 5 vertices and random edges. Then it prints out the adjacency matrix.

#include <iostream>
#include <ctime>
 
using namespace std;
 
#define VERT (5)
 
int adjmat[VERT][VERT];
 
int main()
{
    srand((unsigned)time(0)); //seed random generator
 
    for(int i=0; i<VERT; i++) {
        for(int j=i; j<VERT; j++) {
            adjmat[i][j] = adjmat[j][i] = rand()%2; //set entry to either 0 or 1
        }
    }
 
    for(int i=0; i<VERT; i++) {
        for(int j=0; j<VERT; j++) {
            cout << adjmat[i][j] << " "; //print entry
        }
        cout << endl;
    }
    return 0;
}

Adj. List

This creates a graph with 5 vertices and random edges. Then it prints out the adjacency list.

#include <iostream>
#include <ctime>
#include <vector>
 
using namespace std;
 
#define VERT (5)
 
vector<int> adjlist[VERT];
 
int main()
{
        srand((unsigned)time(0)); //seed random generator
 
        for(int i=0; i<VERT; i++) {
                for(int j=0; j<VERT; j++) {
                        if(rand()%2)
                                adjlist[i].push_back(j); //50% of the time add j to i's edge list
                }
        }
 
        for(int i=0; i<VERT; i++) {
                cout << i << ": "; //print which vertex's edge list follows
                for(int j=0; j<adjlist[i].size(); j++) {
                        cout << adjlist[i][j] << " "; //print each item in edge list
                }
                cout << endl;
        }
        return 0;
}