A graph is an abstract data type representing relations or connections between objects(like cities are connected by rough road). In the graph and its representation, basically, the relation is denoted by edges and objects by vertices(nodes). A graph consists of a finite set of vertices and edges. A graph is a non-linear Data Structure. Let’s take an example of Facebook, we all aware that friends are in a bidirectional relationship on Facebook, if A is a friend of B then B is also the friend of A. The group of friends in which each friend is the friend of remaining friends is an example of Undirected Graph.
Table of Contents
Figure 1: A undirected graph consists of vertices={1,2,3,4,5,6} and edges={12,14,23,35,45,56}
- Nodes/Vertices: It’s like entities whose relationship is defined by edges.
- Edges: It’s like components that represent the relationship between nodes/vertices.
Types of Graphs
- Undirected Graph: It’s a set of objects(nodes/vertices) that are connected together by edges which are bidirectional in nature(See Figure 1).
- Directed Graph: It’s a set of objects(nodes/vertices) that are connected together by edges, where all the edges are directed from one node to another(See Figure 2).
- Weighted Graph: It’s a set of objects(nodes/vertices) that are connected together by edges, where each edge of a graph has an associated numerical value called a weight(See Figure 3).
Figure 2: Directed Graph Figure 3: Weighted Graph
Implementation of Graph
There are different ways to optimally represent a graph, depending on the density of its edges and the type of operations we want to perform.
Adjacency Matrix
It’s a connection matrix of size V*V where V is the total number of vertices that contains only 0,1. Where i is adjacent to j and 1 <= i, j<=V then its value is 1 otherwise 0. Let us see some example of adjacency matrix:
Undirected graph adjacency matrix Directed graph adjacency matrix Weighted graph adjacency matrix
(See Fig. 1) (See Fig. 2) (See Fig. 3)
NOTE: If there is no self-loop in the graph then all cells where i=j must be 0(See above matrices).
/*C++ Implementation of adjacency matrix for undirected graph*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int nodes,edges;
cin>>nodes>>edges;
int adj_matrix[nodes+1][nodes+1];
memset(adj_matrix,0,sizeof(adj_matrix));
for(int i=0;i<edges;i++)
{
int x,y;
cin>>x>>y;
adj_matrix[x][y]=1;
adj_matrix[y][x]=1;// for directed graph we don't write for y->x;
}
/*Print the adjacency matrix*/
for(int i=1;i<=nodes;i++)
{
for(int j=1;j<=nodes;j++)
{
cout<<adj_matrix[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
/* TIME COMPLEXITY: O(N*N) WHERE N IS THE NUMBER OF NODES IN GRAPH */Adjacency List
It’s a linked representation that contains N (total nodes) lists in which each list describes the set of neighbors of a vertex in the graph. The size of the list (for any vertex) is equal to the degree of that vertex.
Directed graph Adjacency List(See fig. 2)
/*C++ Implementation of adjacency list for directed graph using STL*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int nodes,edges;
cin>>nodes>>edges;
vector<int> v[nodes+1];
for(int i=0;i<edges;i++)
{
int x,y;
cin>>x>>y;
v[x].push_back(y); /* add v[y].push_back(x) also for undirected graph beacuse edge is bidirectional in nature*/
}
/*Print the adjacency matrix*/
for(int i=1;i<=nodes;i++)
{
int degree=v[i].size();
for(int j=0;j<degree;j++)
{
cout<<v[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
/* TIME COMPLEXITY: O(V+E) WHERE V IS THE NUMBER OF VERTICES/NODES IN GRAPH AND E IS THE NUMBER OF EDGES */