Home Data Structures Representation of a Graph using Adjacency List and Adjacency Matrix

Representation of a Graph using Adjacency List and Adjacency Matrix

In computer science graph is a data structure consisting of vertices and edges. It is usually written as G(V, E) where V is a set of vertices and E is the set of all the edges.

We have two ways of representing a graph:

  1. Adjacency List Representation (for a sparse graph)
  2. Adjacency Matrix Representation (for a dense graph)

Adjacency List: In adjacency list representation we have a list of sizes equals to total no. of vertices. Each entry of the list contains another list, which is the set of all the vertices adjacent to the current vertex.

Note 1)For an undirected graph(unlike here) we will add an edge from both, vertex u to vertex v and from vertex v to vertex u.
2) For a weighted graph, we will add and extra weight parameter to the adjacency list representation.

Image result for adjacency list

CPP code for Adjacency List representation:

#include <bits/stdc++.h>
using namespace std;

int add_edge(vector<int> adj_list[], int u, int v){
	adj_list[u].push_back(v);
	//adj_list[v].push_back(u); if it's undirected graph
	return 0;
}

int traverse(int n, vector<int> adj[]){
	for (int i=1; i<n; i++){
		cout<<"vetex "<<i<<" is connected to: ";
		for(int j=0;j<adj[i].size();j++)
			cout<<adj[i][j]<<" ";
		cout<<endl;
	}
}

int main() {
	int n = 6;

	vector<int>adj_list[n];

	add_edge(adj_list,1,2);
	add_edge(adj_list,1,3);
	add_edge(adj_list,1,4);
	add_edge(adj_list,2,3);
	add_edge(adj_list,3,4);
	add_edge(adj_list,4,4);
	add_edge(adj_list,5,2);

	traverse(n, adj_list);

	return 0;
}

 

Adjacency Matrix: In adjacency matrix representation we have an array of size VxV and if a vertex(u) is connected to any other vertex(v) then we set the corresponding entry of the array (a[u][v]) as 1.
Note:1)For a weighted graph, we will represent a[u][v] = w(instead of 1), where w is the weight of the corresponding edge from vertex u to v.
2) If it’s an undirected graph then we will put a[u][v] = a[v][u] = 1 (or w is it’s a weighted graph and w is the edge weight).

Here the adjacency matrix formed for the above graph is:

     1   2   3   4   5
 0   1   1   1   0
0   0   1   0   0
0   0   0   1   0
0   0   0   1   0
0   1   0   0   0

CPP code for Adjacency Matrix representation:

#include<bits/stdc++.h>
using namespace std;

int add_edge(vector<vector<int> >&adj_matrix, int u, int v){
	adj_matrix[u][v]=1;	
	//adj_matrix[v][u]=1; if it's undirected graph
	return 0;
}

int traverse(int n, vector<vector<int> >adj_matrix)
{
	for (int i=1; i<n; i++){
		cout<<"vetex "<<i<<" is connected to: ";
		for(int j=1;j<n;j++){
			if(adj_matrix[i][j]==1)
				cout<<j<<" ";
		}
		cout<<endl;
	}
	return 0;
}

int main() {
	int n = 6;

	vector<vector<int> > adj_matrix(n, vector<int> (n));

	add_edge(adj_matrix,1,2);
	add_edge(adj_matrix,1,3);
	add_edge(adj_matrix,1,4);
	add_edge(adj_matrix,2,3);
	add_edge(adj_matrix,3,4);
	add_edge(adj_matrix,4,4);
	add_edge(adj_matrix,5,2);

	traverse(n, adj_matrix);

	return 0;
}

Output for both the programs:

vetex 1 is connected to: 2 3 4
vetex 2 is connected to: 3
vetex 3 is connected to: 4
vetex 4 is connected to: 4
vetex 5 is connected to: 2

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here