yes pagal
#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.
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......................
bag
#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; }
#include #include #include #define max 10 struct node { int vertex; struct node *next; }; typedef struct node* nodeptr; typedef struct queue { int front,rear; int arr[max]; }; typedef struct stack { int top; int arr[max]; }; nodeptr getnode() { nodeptr p;p=(nodeptr)malloc(sizeof(struct node)); p->next=NULL; return p; } int empty(struct stack *s) {if(s->top==-1) { return 1; }else return 0; } void push(struct stack *s,int x) {if(s->top==max-1)printf("\n Queue Overflow"); else {s->top++;s->arr[s->top]=x; } } int pop(struct stack *s) { int x;if(empty(s)) printf("\n Queue Overflow..!"); else {x=s->arr[s->top];s->top--; } return x; } int qempty(struct queue *q) {if(q->front > q->rear)return 1; else return 0; } void insertq(struct queue *q,int x) {if(q->rear==max-1)printf("\n Queue Overflow..1"); else {q->rear++;q->arr[q->rear]=x; } } int removeq(struct queue *q) { int x;if(qempty(q)) printf("\n Queue Overflow..!"); else {x=q->arr[q->front];q->front++; } return x; } void init(nodeptr head[],int n) { int v;for(v=1;vvertex=v2;p=head[v1]; if(p==NULL)head[v1]=new1; else {while(p->next!=NULL)p=p->next;p->next=new1; }if(c==1) {new1=getnode();new1->vertex=v1;p=head[v2]; if(p==NULL)head[v2]=new1; else {while(p->next!=NULL)p=p->next;p->next=new1; } } printf("\n Do You Want To Add More Edges In Graph(y/n):\t");ch=getche(); }while(ch=='y'ch=='Y'); } void display(nodeptr head[],int n) { int v;nodeptr adj; printf("\n Adjancency List Is:\n");for(v=1;vvertex);adj=adj->next; } printf("\n"); } } void DFSR(nodeptr head[],int start,int visited[]) { nodeptr adj;visited[start]=1; printf("\t %d",start); adj=head[start];while(adj!=NULL) {if(visited[adj->vertex]==0) {DFSR(head,adj->vertex,visited); } adj=adj->next; } } void DFSN(nodeptr head[],int start,int visited[]) { nodeptr adj; struct stack s; int v; s.top=-1;push(&s,99);visited[start]=1; printf("\n %d",start); push(&s,start);do { adj=head[start];while(adj!=NULL) {if(visited[adj->vertex]==0) {visited[adj->vertex]=1;printf("\t%d",adj->vertex);push(&s,adj->vertex);start=adj->vertex; break; } else adj=adj->next; }if(adj==NULL) {start=pop(&s); } }while(!empty(&s)); } void BFS(nodeptr head[],int start,int visited[]) { nodeptr adj; struct queue q; int v;q.front=0; q.rear=-1;visited[start]=1; printf("\n %d",start);insertq(&q,start);while(!qempty(&q)) {v=removeq(&q);adj=head[v]; while(adj!=NULL) { if(visited[adj->vertex]==0) { visited[adj->vertex]=1;printf("\t %d",adj->vertex); }adj=adj->next; } } } void main() {char c='y'; int ch,start,n,visited[10]; nodeptr head[10]; clrscr(); do {clrscr(); printf("\n========Graph========");printf("\n 1. Create"); printf("\n 2. Display Adjancency List"); printf("\n 3. Depth First Search(Rec)"); printf("\n 4. Depth First Search(Non-Rec)"); printf("\n 5. Breadth First Search"); printf("\n 6. Exit");printf("\n====================="); printf("\n Enter Your Choice:\t");scanf("%d",&ch); switch(ch) { case 1: printf("\n Enter The No. of Vertices In Graph:\t"); scanf("%d",&n);init(head,n); create(head);break; case 2: display(head,n);break; case 3: printf("\n Enter The Vertex From Which You Want To Start Traversal");scanf("%d",&start);initialise_visit(visited,n); printf("\n Recursive Depth First Search Is\n");DFSR(head,start,visited); break;case 4: printf("\n Enter The Vertex From Which You Want To Start Traversal");scanf("%d",&start);initialise_visit(visited,n); printf("\n Non-Recursive Depth First Search Is\n");DFSN(head,start,visited); break;case 5: printf("\n Enter The Vertex From Which You Want To Start Traversal");scanf("%d",&start);initialise_visit(visited,n);BFS(head,start,visited); break;case 6: break; } printf("\n Do You Want To Continue(y/n):\t"); c=getche(); }while(c=='Y'c=='y'); getch(); }
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.
dfs better then from bfs..
The population of BFS Group Ltd is 4,200.
No. why
#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.
Banking & Financial Sector
No you don't.
going to the gym,daily.
bfs
nop
DFS and BFS are both searching algorithms. DFS, or depth first search, is a simple to implement algorithm, especially when written recursively. BFS, or breadth first search, is only slightly more complicated. Both search methods can be used to obtain a spanning tree of the graph, though if I recall correctly, BFS can also be used in a weighted graph to generate a minimum cost spanning tree.
2,5,4,6,8,9,10