Graph representation : adjacency list and matrix

Graphs representation : Adjacency list and adjacency matrix

A graph is collection of edges E [e1,e2,e3…..en] and vertices V = [v1,v2,v3…vn]. Mathematically, graph is represented as  G = (V,E). An edge is pair of vertices (vi, vj) where i,j <= N. There are many applications of graph in computer science, like representing connection of roads, flight paths, internet etc. In this post, we will learn graph representation in computer programs.Before that, let’s see some terminology.

Undirected and directed graphs
A graph can be undirected or directed graph. A directed graph is where edge is only one way from one vertex to another, whereas undirected graph has two way edges; that is, there is no arrow head at the end of edge.

Number of edges
A directed graph can have at most N2 edges, one of each pair, while undirected graph will have C(N+1,2) edges. Sparse graph is a graph where number of edges is less than N2 and C(N+1,2) for directed and indirected graph respectively.

Paths
Path in a graph is a sequence of vertices [v1,v2….Vk] such that there exists an edge between consecutive vertices. Formally, v1,v2,…vk is a path if (vi, vi+1) belongs to edges.

In-degree and out-degree
In-degree of a vertex is number of edges which end on vertex. Out-degree is number of edges going out of vertex. Let’s see how this terminology applies for below graph.

graph representation

Vertex list v = {1,2,3,4,5,6}
Edge list e = {(2,1)(2,6)(1,4)(4,3)(3,5)(3,6)(5,6)}
Path p = {1,4,3,5,6}
In degree of 3 is 1, out degree of 3 is 2

Adjacency matrix graph representation

In adjacency matrix representation, two dimensional matrix is used to represent graph. Matrix(i,j) is set to true if there is an edge between vertex i and vertex j.

adjacency matrix graph representation

Advantage of adjacency matrix representation is that it is very simple to implement. However, when number of edges between vertices are sparse, lot of cells remain vacant in matrix which lead to wastage of space.
Complexity of graph algorithms is measured in terms of E and V where E is number of edges and V is number of vertices.
In adjacency matrix representation, memory used to represent graph is O(V2).

There are some optimization which are done to save space. For example, if graph is undirected, an edge between (u,v) is also an edge between (v,u). In that case, transpose of adjacency matrix is same as original. We can save half of space while representing an undirected graph using adjacency matrix. Moreover, if there are no weighted edges in graph, instead of using one byte per edge, use only one bit to indicate edge.

#include<stdio.h>
#include<stdlib.h>
 
#define NUM_NODE 6
#define true 1
#define false 0
 
unsigned short adjacencyMatrix[NUM_NODE+1][NUM_NODE+1];
 
void addEdge(int u, int v){
	adjacencyMatrix[u][v] = true;
}
 
int main(){
 
    for(int i=0; i<=NUM_NODE; i++){
    	for(int j=0; j<=NUM_NODE; j++){
    		adjacencyMatrix[i][j] = false;
    	}
    }
 
    addEdge(1,4);
    addEdge(2,1);
    addEdge(2,6);
    addEdge(4,3);
    addEdge(3,6);
    addEdge(3,5);
    addEdge(5,6);
 
    // Adjacency matrix based representation       
    for(int i=1; i<=NUM_NODE; i++){
    	printf("Nodes adjacent to %d : ", i);
    	for(int j=1; j<=NUM_NODE; j++){
    		if(adjacencyMatrix[i][j] == true){
    			printf("%d ", j);
    		}
    	}
    	printf("\n");
    }
 
    return 0;
}

Adjacency list graph graph representation

In adjacency list representation of graph, a table of all vertices of graph is maintained. Each entry in that table will have list of vertices which it is connected to (all it’s neighbors in graph). It is useful where graph is sparse.

adjacency list representation of graph

Memory required for this graph representation is O( V +E ). Adjacency list representation can be easily extended to represent graphs with weighted edges. Node contains another parameter wt. For edge (u,v) node in adjacency list of u will have weight of edge.

#include<stdio.h>
#include<stdlib.h>
 
#define NUM_NODE 6
 
typedef struct node{
        int value;
        struct node *next;
}Node;
 
Node *graph[NUM_NODE];
 
Node *createNode(int j){
	Node * newNode = (Node *)malloc(sizeof(Node));
	if(newNode){
		newNode->value = j;
		newNode->next = NULL;
	}
	else{
		printf("\n Node cannot be allocated");
	}
	return newNode;
}
 
void addEdge(int i, int j){
	Node * currentNode = graph[i];
	if(!currentNode){
	    graph[i] = createNode(j);
	}
	else{
	    while(currentNode->next){
	        currentNode = currentNode->next;
	    }
	    currentNode->next = createNode(j);
	}
}
 
int main(){
 
    addEdge(1,4);
    addEdge(2,1);
    addEdge(2,6);
    addEdge(4,3);
    addEdge(3,6);
    addEdge(3,5);
    addEdge(5,6);
 
    // Adjacency list based representation       
    for(int i=1; i<=NUM_NODE; i++){
    	printf("Nodes adjacent to %d : ", i);
    	Node * current  = graph[i];
    	while(current){
    		printf("%d ", current->value);
    		current = current->next;
    	}
    	printf("\n");
    }
 
    return 0;
}

Please share if there is something wrong or missing. Also, if you want to contribute to website by sharing your knowledge, please write to us, we would love to have you as contributor.