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.

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
 1   0   1   1   1   0
 2   0   0   1   0   0
 3   0   0   0   1   0
 4   0   0   0   1   0
 5   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