#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct adjlistnode{ int adj_node_val;
adjlistnode *next;
};
struct adjlist{ adjlistnode*head;
};
struct grph{ int no_of_vertices;
adjlist *array;
};
adjlistnode *create_new_adj_list_node(int val)
{
adjlistnode *t = new adjlistnode;
t->adj_node_val = val;
t->next = NULL;
return t;
}
grph *create_grph(int v)
{
grph *t=new grph;
t->no_of_vertices = v;
t->array = new adjlist[v];
for(int i=0;i<v;i++)
{
t->array[i].head = NULL;
}
return t;
}
void add_node(grph *t,int src,int des)
{
adjlistnode * temp = create_new_adj_list_node(des);
temp->next = t->array[src].head;
t->array[src].head = temp;
/*
adjlistnode * temp1 = create_new_adj_list_node(src);
temp1->next = t->array[des].head;
t->array[des].head = temp1;
*/
cout<<" Edge created between "<<src<<" and "<<des<<endl;
}
void print_graph(grph *t)
{
for(int i=0;i<t->no_of_vertices;i++)
{
adjlistnode * temp = t->array[i].head;
while(temp)
{
cout<<i<<"---------->"<<temp->adj_node_val<<endl;
temp=temp->next;
}
}
}
void bfs(grph *t)
{
queue<int > q;
vector<int> visited;
q.push(0);
visited.push_back(0);
while(!q.empty())
{
int j = q.front();
cout<<j<<endl;
q.pop();
adjlistnode* temp = t->array[j].head;
while(temp)
{
int k=temp->adj_node_val;
if(find(visited.begin(),visited.end(),k)==visited.end())
{
q.push(k);
visited.push_back(k);
}
temp=temp->next;
}
}
}
int main()
{
grph * t = create_grph(5);
add_node(t,0,3);
add_node(t,2,3);
add_node(t,1,2);
add_node(t,3,4);
add_node(t,0,1);
bfs(t);
print_graph(t);
return 0;
}
