Leveraging ChatGPT - GenAI as a Microsoft Data Expert

Speaker

Prerita Agarwal

Data Specialist @

23 Jul, 2024 @ 01:30 PM

Introduction

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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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 Graph 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;
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 Algorithm)

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];
}
}

A graph is a non-linear data structure consisting of nodes (also known as vertices) and edges. The nodes represent entities, while the edges represent relationships between those entities.

What is the difference between a graph and a tree?

A tree is a type of graph that is always connected and has no cycles. In other words, a tree is a special case of a graph. Graphs, on the other hand, can have cycles and may not necessarily be connected.

What are some common algorithms for graph traversal?

There are two main algorithms for graph traversal: depth-first search (DFS) and breadth-first search (BFS). DFS is a recursive algorithm that explores as far as possible along each branch before backtracking, while BFS explores the graph layer by layer, visiting all the neighbors of a node before moving on to the next level.

What is the shortest path problem in graph theory?

The shortest path problem is the problem of finding the shortest path between two nodes in a graph. The most common algorithm for solving this problem is Dijkstra's algorithm, which uses a priority queue to explore the graph in a greedy manner.

Conclusion

This article discussed Graph Implementation using STL with all the crucial aspects necessary to implement it. We have also discussed the algorithm in detail and implemented the graph. We also learnt the time and space complexity of the program.