Graph Implementation using STL

Graph Implementation using STL
Graph Implementation using STL

A graph is a data structure which is used to implement or store paired objects and their relationships with each other. It consists of two main components:

  • Vertex/Nodes: These are used to represent the objects. E.g. Let us consider a graph of cities where every node is a city. Let A and B be two such cities represented by two nodes A and B.
  • Edges: These represent relationships between those objects. E.g. Let the roads connecting these cities be considered as the relationship that they hold with each other i.e. the edge. One more parameter can be considered which is called the weight. If the roads consist of values like the distance then we can say to reach from city A to B we require some D distance, where D becomes the weight of the edge between A and B.

Applications of Graphs:

  • Maps: Geographical maps shows various places and routes, routes being the edges of the place nodes. E.g. Google maps
  • Social Networks: Let us consider Facebook where every profile is treated as a node and their friendships(relationship) as the edge between two profiles.
  • E-Commerce Recommendation System: We all have seen the recommendation system in an e-commerce site like Flipkart, Amazon etc, which uses the same graphs for finding the recommendations for the particular product we have visited recently.

Types of Graphs:

  • Undirected Graphs: These types of graphs have bidirectional relationships. E.g. let the two cities be connected by a bidirectional road i.e. we can go from A to B and also from B to A.
  • Directed Graphs: These types of graphs have only one-way connectivity. E.g. if A is connected to B does not necessarily mean B is connected to A. Mostly these types are represented with arrowheads. Below we can go from a to b but not from B to A.
  • Unweighted Graphs: These types of graphs have edges without any weights i.e. let say there is uniform cost for going from one edge to another.
  • Weighted Graphs: These types of graphs have edges with weights i.e. let say there is a cost incurred for going from one edge to another.
  • Cyclic Graphs:These types of graphs have edges connected in cyclic order. E.g. b-c-d-e contains a cycle.

Implementation of Graph

Now we can represent graph generally in two ways:

  • Adjacency Matrix
  • Adjacency List

Let us first discus the implementation of Graph using Adjacency Matrix:

Adjacency Matrix Implementation: In this method, we consider a matrix of vertices which contains the relationship information in the matrix i.e. if a vertex u is connected to vertex v the there will be an edge/relationship at matrix[u][v] and it might be bidirectional or unidirectional weighted or unweighted depending up the need of the problem.

Implementation:

struct Graph {
int V;
int E;
int** Adj;
};
struct Graph *adjMatrixOfGraph(){
int i,u,v;
Graph *G = new Graph;
// cout<<“Enter no. of Vertices “; cin>>G->V;
//cout<<“Enter no. of Edges “; cin>>G->E;

G->Adj = new int*[G->V];
for(int j = 0;j<G->V;j++)
    G->Adj[j] = new int[G->V];
for(int u = 0 ;u<G->V;u++)
    for(int v = 0;v<G->V;v++)
        G->Adj[u][v] = 0;

for(int i = 0;i<G->E;i++)
{
    //Undirected Graph
    //cout<<"Enter edge pair: _%d_%d_ ";
    //for directed graph adj(u,v) gives only the edge u->v 
    cin>>u>>v;
        G->Adj[u][v] = 1;
        G->Adj[u][v] = 1;
}
return G;

}

Here we can also travel the Graph using Breadth First Search(BFS):

struct Graph {
int V;
int E;
int** Adj;
};
struct Graph createAdjMatrix(int V,int E) { struct Graph G = new Graph;
G->V = V;
G->E = E;
G->Adj = new int*[G->V];
for(int i = 0;iV;i++)
{
G->Adj[i] = new int[G->V];
for(int j = 0;jV;j++)
G->Adj[i][j] = 0;
}
for(int i = 0;iE;i++)
{
int u,v;
cin>>u>>v;

    G->Adj[u][v] = 1;
    G->Adj[v][u] = 1;
}
return G;    

}
void BFS(struct Graph* G,int u,bool* visited){
queue q;
q.push(u);
visited[u] = true;

blog banner 1
while(!q.empty()){
    int currentVertex = q.front();
    q.pop();
    cout<<currentVertex<<" ";

    for(int i = 0;i<G->V;i++)
    {
        if(i==currentVertex)
            continue;
        if(!visited[i] && G->Adj[currentVertex][i])
        {
            q.push(i);
            visited[i] = true;
        }
    }
}

}
void BFSutil(struct Graph* G)
{
bool* visited = new bool[G->V];
for(int i = 0;iV;i++)
visited[i] = false;

for(int i = 0;i<G->V;i++)
    if(!visited[i])
        BFS(G,i,visited);

}

Let us see traversal of graph using Depth First Search (DFS):

struct Graph {
int V;
int E;
list *Adj; // list of vertices

/* Using a List which acts as a Doubly Linked List the input pattern or the order in which input in done effects the DFS traversal. Mostly to achieve a proper DFS traversal using a list we need to take inputs in the Depth First Order */

};
struct Graph *createAdjList(){
struct Graph *G = new Graph;
cin>>G->V;
G->Adj = new list[G->V];
cin>>G->E;

for(int i =0;i<G->E;i++)
{
    int u,v;
    cin>>u>>v;
    //Directed Graph
    G->Adj[u].push_back(v);
    //G->Adj[v].push_back(u);
}

return G;

}
void DFSUtil(struct Graph *G,int u,vector& visited){
cout<<u<<” “;
visited[u] = true;

for(auto i = G->Adj[u].begin();i!=G->Adj[u].end();i++)
    if(!visited[*i])
        DFSUtil(G,*i,visited);

}
void DFS(struct Graph* G){
vector visited(G->V,false);
//this will also take care of disconnected graphs
for(int i = 0;iV;i++)
if(!visited[i])
DFSUtil(G,i,visited);
}

Space Complexity: Where V is the number of vertices. These are the two ways of traversal in Graph using adjacency matrix. This method is a very space-consuming method for sparse graphs. Hence to reduce the space complexity we use Adjacency List.

Adjacency List Implementation: Here we take the help of list data structure (STL) in C++, which works on the basis of linked list implementation. Each vertex consists of a list of vertices which are connected to the particular vertex. Let us see the implementation.

Implementation with BFS travel:

class Graph{
int V;
//array of lists
list *adjList;
public:
Graph(int v){
V = v;
adjList = new list[V];
}
void addEdge(int u,int v,int bidir = true){
adjList[u].push_back(v);
if(bidir)
adjList[v].push_back(u);
}
void printAdjList(){
for(int i = 0;i”;
for(auto element : adjList[i])
cout< q;
bool *visited = new bool[V]{false};
q.push(src);
visited[src] = true;
int *dist = new int[V]{0};
int *parent = new int[V];
for(int i = 0;i”;
temp = parent[temp];
}
}

Implementation of the DFS traversal:

void dfsUtil(int src,bool* visited){
cout<<src;
visited[src] = true;
for(auto nbr : adj[src]){
if(!visited[nbr])
dfsUtil(nbr,visited);
}
}
void dfs(int src){
bool *visited = new bool[V];
for(int i = 0;i<V;i++)
visited[i] = false;
dfsUtil(src,visited);
}

Space Complexity: Where E is the number of edges. Hope this helps aspiring software developers and programmers.

To read more about Data Structures, click here.

By Aniruddha Guin