0
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<process.h>
#include<string.h>
#define MAX 20
typedef struct queue
{
int data;
struct queue *next;
}queue;
typedef struct stack
{
int data;
struct stack *next;
}stack;
typedef struct adj_list
{
int vertex;
struct adj_list *next;
}adj_list;
adj_list *G[MAX];
int queue_empty(queue *front,queue *rear)
{
if(front==NULL && rear==NULL)
return 1;
else
return 0;
}
queue* getnode()
{
queue *newnode;
newnode = (queue*)malloc(sizeof(queue));
newnode->next = NULL;
return newnode;
}
void enqueue(queue **front, queue **rear, int data)
{
queue *newnode;
newnode = getnode();
newnode->data = data;
if(queue_empty(*front,*rear))
{
*front = *rear = newnode;
}
else
{
(*rear)->next = newnode;
(*rear) = newnode;
}
}
int dequeue(queue **front,queue **rear)
{
int data;
queue *temp;
if(queue_empty(*front,*rear))
return 0;
temp = *front;
data = (*front)->data;
if(*front==*rear)
{
*front = *rear = NULL;
}
else
{
*front = (*front)->next;
}
free(temp);
return data;
}
stack* create_node()
{
stack *newnode;
newnode = (stack*)malloc(sizeof(stack));
newnode->next = NULL;
return newnode;
}
void push(stack **top, int data)
{
stack *newnode;
newnode = create_node();
newnode->data = data;
newnode->next = *top;
*top = newnode;
}
int pop(stack **top)
{
stack *temp;
int data;
temp = *top;
data = (*top)->data;
*top = (*top)->next;
free(temp);
return data;
}
int stack_empty(stack *top)
{
if(top==NULL)
return 1;
else
return 0;
}
void insert(int vi, int vj)
{
adj_list *temp,*newnode;
newnode=(adj_list*)malloc(sizeof(adj_list));
newnode->vertex = vj;
newnode->next=NULL;
if(G[vi]==NULL)
{
G[vi]=newnode;
}
else
{
temp = G[vi];
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = newnode;
}
}
void create(int count,char location[MAX][MAX])
{
int i,edges, vi,vj;
for(i=0;i<count;i++)
{
printf("\nEnter the name of node %d\t",i);
flushall();
scanf("%s",location[i]);
G[i] = NULL;
}
printf("\nEnter number of edges\t");
scanf("%d",&edges);
for(i=0;i<edges;i++)
{
printf("\nEnter the edge (node u,node v)\t");
scanf("d",&vi,&vj);
insert(vi,vj);
insert(vi,vj);
}
}
void BFS(int v,int count,char location[MAX][MAX])
{
int w,i,visited[MAX];
queue *front=NULL,*rear=NULL;
adj_list *temp;
for(i=0;i<count;i++)
{
visited[i]=0;
}
enqueue(&front,&rear,v);
printf("\n%s",location[v]);
visited[v]=1;
while(!queue_empty(front,rear))
{
v = dequeue(&front,&rear);
for(temp=G[v];temp!=NULL;temp=temp->next)
{
w = temp->vertex;
if(visited[w]==0)
{
enqueue(&front,&rear,w);
visited[w]=1;
printf("\n%s",location[w]);
}
}
}
}
void DFS(int v,int count,char location[MAX][MAX])
{
adj_list *temp;
int visited[MAX],j,w;
stack *top=NULL;
for(j=0;j<count;j++)
{
visited[j]=0;
}
push(&top,v);
visited[v]=1;
while(!stack_empty(top))
{
w = pop(&top);
printf("\n%s",location[w]);
for(temp=G[w];temp!=NULL;temp=temp->next)
{
if(visited[temp->vertex]==0)
{
push(&top,temp->vertex);
visited[temp->vertex]=1;
}
}
}
}
int search(char location[MAX][MAX], char item[MAX])
{
int i;
for(i=0;i<MAX;i++)
{
if(stricmp(item,location[i])==0) /*string found*/
return i;
}
return -1;
}
void main()
{
int ch,count,i;
char location[MAX][MAX],start[MAX];
do
{
clrscr();
printf("\n*** MENU ***");
printf("\n1.Create");
printf("\n2.Depth First Search");
printf("\n3.Breadth First Search");
printf("\n4.Exit");
printf("\n\nEnter your choice\t");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter number of nodes\t");
scanf("%d",&count);
create(count,location);
break;
case 2:
printf("\nEnter starting place\t");
scanf("%s",start);
i = search(location,start);
if(i==-1)
printf("\nInvalid Location Entered");
else
{
printf("\nDepth First Search...\n");
DFS(i,count,location);
}
break;
case 3:
printf("\nEnter starting place\t");
scanf("%s",start);
i = search(location,start);
if(i==-1)
printf("\nInvalid Location Entered");
else
{
printf("\nBreadth First Search...\n");
BFS(i,count,location);
}
break;
case 4:exit(0);
default:printf("\nPlease enter proper choice!!!");
}
getch();
}while(1);
}
This program performs both DFS and BFS operations.
What else can I help you with?
Prove that if a DFS and BFS trees in graph G are the same than?
ok here we go...Proof:If the some graph G has the same DFS and BFS then that means that G should not have any cycle(work out for any G with a cycle u will never get the same BFS and DFS .... and for a graph without any cycle u will get the same BFS/DFS).We will prove it by contradiction:So say if T is the tree obtained by BFS/DFS, and let us assume that G has atleast one edge more than T. So one more edge to T(T is a tree) would result in a cycle in G, but according to the above established principle no graph which has a cycle would result the same DFS and BFS, so out assumption is a contradiction.Hence G should have more edges than T, which implies that if the BFS and DFS for a graph G are the same then the G = T.Hope this helps u......................
Why BFS is implemented using queue and DFS is implemented using stack?
yes pagal
Explain why there are no forward non tree edges with respect to a BFS tree constructed for a directed graph?
bag
How do you implement depth first search in C using arrays?
#include<stdio.h> #include<conio.h> char que[20]; int front=0, rear=0, n; char arr[20]; int bfs(int ); char ajMat[20][20]; char b[20]; void display(); int p=0; int main() { char v; printf("Enter the number of nodes in a graph"); scanf("%d",&n); printf("Enter the value of node of graph"); for(int i=0; i<n; i++) { scanf("%s",&b[i]); } printf("Enter the value in adjancency matrix in from of 'y' or 'n'\n"); printf("If there exits an edge between two vertices than 'y' otherwise 'n'\n"); for(int i=0; i<n; i++) printf(" %c ",b[i]); for(int i=0;i<n; i++) { printf("\n%c ",b[i]); for(int j=0; j<n; j++) { printf("%c ",v=getch()); ajMat[i][j]=v; } printf("\n\n"); } for(int i=0;i<n;i++) bfs(i); display(); getch(); } void display() { printf("BFS of Graph : "); for(int i=0; i<n; i++) printf("%c ",arr[i]); } void insert(char val) { que[front]=val; front++; } char del() { rear=rear+1; return que[rear-1]; } bool unVisit(char val) { for(int i=0; i<front; i++) { if(val==que[i]) return false; } return true; } int bfs(int i) { char m; if(front==0) { insert(b[i]); } for(int j=0; j<n; j++) { if(ajMat[i][j]=='y') { if(unVisit(b[j])) { insert(b[j]); } } } m=del(); arr[p]=m; p++; return 0; }
Program that implements breadth first search algorithm?
#include <stdio.h> #include <conio.h> #include <malloc.h> #define TRUE 1 #define FALSE 0 #define MAX 8 struct node { int data ; struct node *next ; } ; int visited[MAX] ; int q[8] ; int front, rear ; void bfs ( int, struct node ** ) ; struct node * getnode_write ( int ) ; void addqueue ( int ) ; int deletequeue( ) ; int isempty( ) ; void del ( struct node * ) ; int main( ) { struct node *arr[MAX] ; struct node *v1, *v2, *v3, *v4 ; int i ; v1 = getnode_write ( 2 ) ; arr[0] = v1 ; v1 -> next = v2 = getnode_write ( 3 ) ; v2 -> next = NULL ; v1 = getnode_write ( 1 ) ; arr[1] = v1 ; v1 -> next = v2 = getnode_write ( 4 ) ; v2 -> next = v3 = getnode_write ( 5 ) ; v3 -> next = NULL ; v1 = getnode_write ( 1 ) ; arr[2] = v1 ; v1 -> next = v2 = getnode_write ( 6 ) ; v2 -> next = v3 = getnode_write ( 7 ) ; v3 -> next = NULL ; v1 = getnode_write ( 2 ) ; arr[3] = v1 ; v1 -> next = v2 = getnode_write ( 8 ) ; v2 -> next = NULL ; v1 = getnode_write ( 2 ) ; arr[4] = v1 ; v1 -> next = v2 = getnode_write ( 8 ) ; v2 -> next = NULL ; v1 = getnode_write ( 3 ) ; arr[5] = v1 ; v1 -> next = v2 = getnode_write ( 8 ) ; v2 -> next = NULL ; v1 = getnode_write ( 3 ) ; arr[6] = v1 ; v1 -> next = v2 = getnode_write ( 8 ) ; v2 -> next = NULL ; v1 = getnode_write ( 4 ) ; arr[7] = v1 ; v1 -> next = v2 = getnode_write ( 5 ) ; v2 -> next = v3 = getnode_write ( 6 ) ; v3 -> next = v4 = getnode_write ( 7 ) ; v4 -> next = NULL ; front = rear = -1 ; bfs ( 1, arr ) ; for ( i = 0 ; i < MAX ; i++ ) del ( arr[i] ) ; getch( ) ; return 0; } void bfs ( int v, struct node **p ) { struct node *u ; visited[v - 1] = TRUE ; printf ( "%d\t", v ) ; addqueue ( v ) ; while ( isempty( ) -1 ) return TRUE ; return FALSE ; } void del ( struct node *n ) { struct node *temp ; while ( n != NULL ) { temp = n -> next ; free ( n ) ; n = temp ; } }
Who is faster between dfs and bfs?
dfs better then from bfs..
What is the population of BFS Group Ltd?
The population of BFS Group Ltd is 4,200.
Can anyone be jb bfs?
No. why
Difference between DFS and BFS?
1. bfs uses queue implementation ie.FIFO dfs uses stack implementation ie. LIFO 2. dfs is faster than bfs 3. dfs requires less memory than bfs 4. dfs are used to perform recursive procedures.
What is the bfs workout?
going to the gym,daily.
WHAT IS BFS meetings?
Banking & Financial Sector
Should you capitalize he is the president of a the BFS?
No you don't.
Is BFS recursive?
No, Breadth-First Search (BFS) is not inherently recursive. It is typically implemented using a queue data structure rather than recursion.
Write a program to solve bfs in c language?
#include<stdio.h> #include<conio.h> int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1; void bfs(int v) { for(i=1;i<=n;i++) if(a[v][i] && !visited[i]) q[++r]=i; if(f<=r) { visited[q[f]]=1; bfs(q[f++]); } } void main() { int v; printf("\n Enter the number of vertices:"); scanf("%d",&n); for(i=1;i<=n;i++) { q[i]=0; visited[i]=0; } printf("\n Enter graph data in matrix form:\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&a[i][j]); printf("\n Enter the starting vertex:"); scanf("%d",&v); bfs(v); printf("\n The node which are reachable are:\n"); for(i=1;i<=n;i++) if(visited[i]) printf("%d\t",i); else printf("\n Bfs is not possible"); getch(); }
Can apply bfs and dfs on weighted graph?
nop
Compare and contrast judaism with mesopotamian religions?
bfs
Can you land into BFS in Microsoft Flight Simulator X?
2,5,4,6,8,9,10
