how to implement graph using adjacency list c++ code example
Example 1: graph c++
#include <bits/stdc++.h>
using namespace std;
class graph
{
vector<int>*adjacency_list;
int Vertices;
public:
graph(int n)
{
Vertices=n;
adjacency_list=new vector<int>[Vertices];
}
void add_edge(int,int);
void display_graph();
};
int main()
{
graph g1(5);
g1.add_edge(0,1);
g1.add_edge(1,2);
g1.add_edge(1,3);
g1.add_edge(2,4);
g1.add_edge(2,3);
cout<<"The entered Graph is "<<endl;
g1.display_graph();
return 0;
}
void graph::add_edge( int u,int v )
{
if( u >= Vertices || v >= Vertices )
{
cout<<"Overflow"<<endl;
return;
}
if( u<0 || v<0 )
{
cout<<"underflow"<<endl;
return;
}
adjacency_list[u].push_back(v);
adjacency_list[v].push_back(u);
}
void graph::display_graph()
{
for(int i=0;i<Vertices;i++)
{
cout<<"Adjacency list of vertex of vertex "<<i<<endl;
for(auto it:adjacency_list[i])
{
cout<<it<<" ";
}
cout<<endl;
}
}
Example 2: weighted graph c++
#include <bits/stdc++.h>
using namespace std;
class WeightedGraph
{
vector< pair<int,int> >*adjacency_list;
int vertices;
public:
WeightedGraph(int n)
{
vertices=n;
adjacency_list=new vector< pair<int,int> >[n];
}
void add_edge(int v1,int v2,int wt);
void dfsHelper(int src,bool visited[]);
void dfs(int src);
void bfs(int src);
int minDistance(vector<int>dist,bool visited[]);
void djisktra(int src);
void display_graph();
};
int main()
{
WeightedGraph wg1(5);
wg1.add_edge(0,1,10);
wg1.add_edge(1,2,20);
wg1.add_edge(2,3,30);
wg1.add_edge(1,3,40);
wg1.add_edge(2,4,100);
wg1.add_edge(4,0,10);
wg1.display_graph();
wg1.dfs(0);
wg1.bfs(0);
for(int i=0;i<5;i++)
{
djikstra(i);
}
return 0;
}
void WeightedGraph::add_edge(int v1,int v2,int wt)
{
adjacency_list[v1].push_back(make_pair(v2,wt));
adjacency_list[v2].push_back(make_pair(v1,wt));
}
void WeightedGraph::dfsHelper(int src,bool visited[])
{
visited[src]=true;
cout<<src<<" ";
for(vector<int>::iterator it=adjacency_list.begin();i!=adjacency_list.end();it++)
{
if(!visited[it->first]);
dfsHelper(it->first,visited);
}
}
void WeightedGraph::dfs(int src)
{
bool visited[vertices];
for(int i=0;i<vertices;i++)
visited[i]=false;
dfsHelper(src,visited);
}
void WeightedGraph::bfs(int src)
{
bool visited[vertices];
for(int i=0;i<vertices;i++)
visited[i]=false;
cout<<src<<" ";
visited[src]=true;
queue<int>helper;
helper.push(src);
while(!helper.empty())
{
src=helper.front();
for(vector<int>::iterator it=adjacency_list[src].begin();it!+adjacency_list[src].end();it++)
{
if(!visited[it->first])
{
visited[it->first]=true;
cout<<it->first<<" ";
helper.push(it->first);
}
}
helper.pop();
}
}
int WeightedGraph::minDistance(vector<int>dist,bool visited[])
{
int min=INT_MAX;
int minIndex=INT_MAX;
for(int i=0;i<N;i++)
{
if(!visited[i]&&dist[i]<=min)
{
min=dist[i];
minIndex=i;
}
}
return minIndex;
}
void WeightedGraph::djikstra(int src)
{
vector<int>dist;
bool visited[vertices];
for(int i=0;i<vertices;i++)
{
dist.push_back(INT_MAX);
visited[i]=false;
}
visited[src]=true;
dist[src]=0;
for(int i=0;i<vertices-1;i++)
{
int k=minDistance(dist,visited);
visited[k]=true;
for(int j=0;j<vertices;j++)
{
if(!visited[i]&&dist[i]!=INT_MAX&&adjacency_list[i][j].second+dist[i]<dist[j])
{
dist[j]=adjacency_list[i][j].second+dist[i];
}
}
}
for(int i=0;i<dist.size();i++)
cout<<dist[i]<<" ";
cout<<endl;
}
void WeightedGraph::display_graph()
{
int a,b;
for(int i=0;i<vertices;i++)
{
cout<<"Adjacency list of vertex "<<i<<endl;
for(auto it=adjacency_list[i].begin();it!=adjacency_list[i].end();it++)
{
a=it->first;
b=it->second;
cout<<"Vertex : "<<a<<" Weight : "<<b<<endl;
}
cout<<endl;
}
}