An Introduction to Graph
Here we are not gonna discuss the definitions of graph and its algorithm we are just going to visualise what graph is and different ways to store the graph.
What is a graph?
It is totally different from the one we see in mathematics. Basically it is a way to represent the relations between a set of entities. This set of entities are called nodes and the relation between any two entities are called edge.
Let us see an example to get the actual visualization of graph. Everyone uses Facebook. Suppose there is a set of people Ankit, Abhishek, Aditya, Akshay who are on Facebook.
i) Ankit is a friend of Aditya and Akshay.
ii) Abhishek is a friend of Akshay only.
iii) Aditya is friend with Ankit only.
iv) Akshay is friend of Ankit and Abhishek.
In the above figure the ovals labeled with the names are called nodes and the lines which represent the relation between two nodes are known as edges and the above figure is called a graph.This edges represent that two connecting nodes are friends with each other.
Storing a graph
Right now we are gonna discuss the two ways to store a graph.
- First we can maintain a table with size N*N where N is number of nodes in the graph. Where each cell of the table will be having either 1 if corresponding row and column are friends or 0 otherwise.
As we can see that the above table is N*N square matrix and this representation is called Adjacency Matrix representation. Which has O(N²) space complexity. For this representation we use a 2-D array of size N².
2. We can maintain a single list for each person which will contain the name of their friends. So the representation would look like.
Ankit -> Aditya, Akshay
Aditya -> Ankit
Akshay -> Ankit, Abhishek
Abhishek -> Akshay
This way of representing a graph is called Adjacency List representation. It has O(N+E) space complexity. Where N represents number of nodes and E represents number of edges in the graph.
A comparison between these two ways of representation
As we can see that adjacency list representation requires less space as compared to adjacency matrix representation, but we can not say that adjacency list representation is the better than adjacency matrix representation because in adjacency matrix representation we use array which is easier to handle for insertion and deletion (if we have created a 2-D array of fixed size N*N we just need to put 0 or 1 in corresponding cell) but insertions and deletions are a bit complex in list as compared to array (for each insertion we will have to create a new list node and insert into the list). So it totally depends upon the type of graph whether it is sparse or dense.
A graph is called dense if the number of edges ( considering each pair of nodes can have max of only one edge between them ) in the graph are close to maximum number of edges in the graph otherwise it is sparse.
So if the graph is sparse then we can use adjacency list representation because in sparse graph we do not have too many edges so this requires less space to be stored. But if the graph is dense then we can use Adjacency matrix representation for convenience.
Directed and Undirected edge
There are multiple types of edges. Here we are gonna discuss these two types of edges.
If the edge has a direction then it is called directed edge otherwise it is called undirected edge.
If two people are friends means they became friends with the mutual consent. So we can not represent this relation in only one direction so we just do not give any direction to the representation and represent it like A — B. This edge is called undirected edge.
Let us take an example, there are a set of people and we want to show who likes whom. Suppose there are two people A and B from the set. We only know that A likes B. So for representing this relation we can use a directed edge which will be having direction from A to B (A -> B ) denoting A likes B.
Suppose if B does not like A then do not have to care about it. If B likes A then we will have to use one separate edge which will have direction from B to A ( B -> A) denoting B likes A.
We can think of an undirected edge as two directed edges.
A — B can be thought as A -> B and B -> A. We will use this concept to store the graph.
Note:- We use List or vector STL for adjacency list representation. We do not have to write code for insertion or deletion we just need to import the library and just some function calls. Read about vector. List is nothing but a linked list. We are going to use Vector for adjacency list representation.
A Sample code for Adjacency List Representation:-
Before proceeding to the code you should have some prior knowledge of vectors.
#include <iostream>
#include <vector>
using namespace std;int main() {
int N; // Number of nodes
int E; // Number of edges
int i,j,sz;
cout<<"Enter the number of nodes in the graph \n";
cout<<"Enter number of edges in the graph:- ";
cin>>N>>E; vector<int > adj_list[N+1];
// each index is a list for the ith node
int a,b;
cout<<"Enter edges as two space separated integers\n";
cout<<"which represents they have an edge between them\n"; for(i=0;i<E;i++) {
cin>>a>>b;
// if edge is undirected then we will need to put b in
// a's list and a in b's list so we will follow below code
adj_list[a].push_back(b);
adj_list[b].push_back(a);
// If the edge is directed as a->b then we will only need
// to put b in a's list and we will follow below code
// adj_list[a].push_back(b);
// We consider the edges to be undirected
} cout<<endl<<"In this graph"<<endl;
for(i=1;i<=N;i++) {
sz=adj_list[i].size();
cout<<i<<" is connected to ";
for(j=0;j<sz;j++){
cout<<adj_list[i][j]<<" ";
}
cout<<endl;
}
return 0;
}Output:-
Enter the number of nodes in the graph 4 3
Enter number of edges in the graph:- Enter edges as two space separated integers
which represents they have an edge between them
1 2
1 3
4 3In this graph
1 is connected to 2 3
2 is connected to 1
3 is connected to 1 4
4 is connected to 3
