Example 1: Graph Adjacent Node in c++
using namespace std;
struct adjNode {
int val, cost;
adjNode* next;
};
struct graphEdge {
int start_ver, end_ver, weight;
};
class DiaGraph{
adjNode* getAdjListNode(int value, int weight, adjNode* head) {
adjNode* newNode = new adjNode;
newNode->val = value;
newNode->cost = weight;
newNode->next = head;
return newNode;
}
int N;
public:
adjNode **head;
DiaGraph(graphEdge edges[], int n, int N) {
head = new adjNode*[N]();
this->N = N;
for (int i = 0; i < N; ++i)
head[i] = nullptr;
for (unsigned i = 0; i < n; i++) {
int start_ver = edges[i].start_ver;
int end_ver = edges[i].end_ver;
int weight = edges[i].weight;
adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
head[start_ver] = newNode;
}
}
~DiaGraph() {
for (int i = 0; i < N; i++)
delete[] head[i];
delete[] head;
}
};
void display_AdjList(adjNode* ptr, int i)
{
while (ptr != nullptr) {
cout << "(" << i << ", " << ptr->val
<< ", " << ptr->cost << ") ";
ptr = ptr->next;
}
cout << endl;
}
int main()
{
graphEdge edges[] = {
{0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
};
int N = 6;
int n = sizeof(edges)/sizeof(edges[0]);
DiaGraph diagraph(edges, n, N);
cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
for (int i = 0; i < N; i++)
{
display_AdjList(diagraph.head[i], i);
}
return 0;
}
Example 2: weighted graph c++
//code by Soumyadeep Ghosh
//insta : @soumyadepp
//linked in: https://www.linkedin.com/in/soumyadeep-ghosh-90a1951b6/
using namespace std;
//undirected weighted graph and all functions
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()
{
//graph of five vertices
WeightedGraph wg1(5);
//adding edges
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);
//displaying the graph
wg1.display_graph();
//dfs from vertex 0
wg1.dfs(0);
//bfs from vertex 0
wg1.bfs(0);
//djikstra
for(int i=0;i<5;i++)
{
djikstra(i);
}
return 0;
}
//function definitions
void WeightedGraph::add_edge(int v1,int v2,int wt)
{
/*push the other vertex into the adjacency list of the given vertex
and vice versa. If it would have been a directed graph,
only the first line would be enough
*/
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;
//first loop to traverse across vertices
for(int i=0;i<vertices;i++)
{
cout<<"Adjacency list of vertex "<<i<<endl;
//second loop to traverse across the adjacency list of some vertex i
for(auto it=adjacency_list[i].begin();it!=adjacency_list[i].end();it++)
{
//set a as the vertex number and b as the weight
a=it->first;
b=it->second;
cout<<"Vertex : "<<a<<" Weight : "<<b<<endl;
}
cout<<endl;
}
}
//thank you!