BFS and DFS in Cpp
The following code demonstrates the use of BFS and DFS in cpp, using data structures Queue and Stack.
#include <iostream>
using namespace std;
/* Date: 24-11-2022 */
int a[7][7]={
{0,1,1,1,0,0,0},
{1,0,1,0,0,0,0},
{1,1,0,1,1,0,0},
{1,0,1,0,1,0,0},
{0,0,1,1,0,1,1},
{0,0,0,0,1,0,0},
{0,0,0,0,1,0,0}
};
int visited[]={
0,0,0,0,0,0,0
};
// Making a queue to use while breadth-first-search
typedef struct q{
int* arr;
int size;
int f,r;
}queue;
bool isFull(queue* q){
if(q->r==q->size-1){
return true;
}
return false;
}
bool isEmpty(queue* q){
if(q->r==q->f){
return true;
}
return false;
}
void enqueue(queue* a,int n){
if(isFull(a)){
cout<<"queue is full.\n";
return;
}
a->r+=1;
a->arr[a->r]=n;
}
int deque(queue* a){
if(isEmpty(a)){
cout<<"queue is empty."<<"\n";
return 0;
}
a->f+=1;
int elem=a->arr[a->f];
// a->f+=1;
return elem;
}
void print_queue(queue* q){
for(int i=q->f+1;i<q->r;i++){
cout<<q->arr[i]<<" ";
}cout<<endl;
}
// char* c=(char*)malloc(sizeof(char)*20);
// int* v=(int*)malloc(sizeof(int)*12);
/* Breadth First Search Traversal- Uses Queue*/
void bfs(int n){
queue* q=(queue*)malloc(sizeof(queue));
q->size=30;
q->arr=(int*)malloc(sizeof(int)*(q->size));
q->f=q->r=-1;
// cout<<"q's f is "<<q->f<<" and q's r is "<<q->r<<endl;
int i=n;
cout<<i<<" ";
visited[i]=1;
enqueue(q,i);
// cout<<"queue arr is:-\n";
// for(int i=0;i<q->size;i++){
// cout<<q->arr[i]<<" ";
// }cout<<endl;
while(!isEmpty(q)){
// cout<<"foo\n";
// cout<<endl;
// cout<<"queue is:- ";
// print_queue(q);
int node=deque(q);
cout<<"\n node is "<<node<<endl;
// cout<<"\nnode is "<<node<<endl;
for(int j=0;j<7;j++){
if(visited[j]!=1 and a[node][j]==1){
cout<<j<<" ";
visited[j]=1;
enqueue(q,j);
}
}
}
cout<<endl;
}
/* Depth First Search Traversal- Uses Stack */
void dfs(int n){
/* This function uses the built-in stack of the
computer which is used to store the function
calls and doesn't require an external stack
*/
int i=n;
cout<<i<<" ";
visited[i]=1;
for(int j=0;j<7;j++){
if(a[i][j]==1 and visited[j]!=1){
/* Means the node(vertex) is not visited and is
connected to the n node(vertex) then we will
call the dst func for that node(vertex)
*/
dfs(j);
}
}
}
int main() {
// for(int i=0;i<20;i++){
// *(c+i)='i';
// }
// for(int i=0;i<20;i++){
// cout<<*(c+i)<<" ";
// }
// cout<<endl;
// cout<<"sizeof(char): "<<sizeof(char)<<endl;
// cout<<"sizeof(char_pointer: "<<sizeof(c)<<endl;
// cout<<"sizeof(int): "<<sizeof(int)<<endl;
// cout<<"sizeof(int_pointer): "<<sizeof(v)<<endl;
// cout<<sizeof(visited)<<endl;
// dfs(0);
bfs(0);
// cout<<"Hola Todo El Mundo!\n";
return 0;
}
Comments
Post a Comment