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:
- what are the graph vertices
- 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
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; }