Program for DFS and BFS of a tree. Comment below if you need help
#include<stdio.h> int adj[50][50]; int visited[50]; void adjcreate(); void dfs(int); void bfs(int); int n; main() { int i, v, ch; adjcreate(); do { printf("\nMENU:\n1.DFS\n2.BFS\n3.Exit\n"); printf("Enter your choice:"); scanf("%d",&ch); switch (ch) { case 1: printf("\nEnter starting node for Depth First Search:"); scanf("%d",&v); for (i=1;i<=n;i++) visited[i]=0; dfs(v); break; case 2: printf("\nEnter starting node for Breadth First Search:"); scanf("%d",&v); for (i=1;i<=n;i++) visited[i]=0; bfs(v); break; case 3: break; default: printf("Wrong choice!\n"); break; } }while(ch!=3); } void adjcreate() { int i,j,ch; printf("Enter number of nodes :"); scanf("%d", &n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("\n Press 1 if %d connected to %d",i,j); scanf("%d",&ch); if(ch==1) { adj[i][j]=1; } else { adj[i][j]=0; } } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf(" %d ",adj[i][j]); printf("\n"); } } void dfs(int v) { int i,stack[50],top=-1,pop; top++; stack[top]=v; while(top>=0) { pop=stack[top]; top--; if(visited[pop]==0) { printf("%d ",pop); visited[pop]=1; } else continue; for(i=n;i>=1;i--) { if(adj[pop][i]==1&&visited[i]==0) { top++; stack[top]=i; } } } } void bfs(int v) { int i,front,rear; int que[50]; front=rear=-1; printf("%d ",v); visited[v]=1; rear++; front++; que[rear]=v; while(front<=rear) { v=que[front]; front++; for (i=1;i<=n;i++) { if (adj[v][i]==1&&visited[i]==0) { printf("%d ",i); visited[i]=1; rear++; que[rear]=i; } } } }
#include<stdio.h> int adj[50][50]; int visited[50]; void adjcreate(); void dfs(int); void bfs(int); int n; main() { int i, v, ch; adjcreate(); do { printf("\nMENU:\n1.DFS\n2.BFS\n3.Exit\n"); printf("Enter your choice:"); scanf("%d",&ch); switch (ch) { case 1: printf("\nEnter starting node for Depth First Search:"); scanf("%d",&v); for (i=1;i<=n;i++) visited[i]=0; dfs(v); break; case 2: printf("\nEnter starting node for Breadth First Search:"); scanf("%d",&v); for (i=1;i<=n;i++) visited[i]=0; bfs(v); break; case 3: break; default: printf("Wrong choice!\n"); break; } }while(ch!=3); } void adjcreate() { int i,j,ch; printf("Enter number of nodes :"); scanf("%d", &n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("\n Press 1 if %d connected to %d",i,j); scanf("%d",&ch); if(ch==1) { adj[i][j]=1; } else { adj[i][j]=0; } } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf(" %d ",adj[i][j]); printf("\n"); } } void dfs(int v) { int i,stack[50],top=-1,pop; top++; stack[top]=v; while(top>=0) { pop=stack[top]; top--; if(visited[pop]==0) { printf("%d ",pop); visited[pop]=1; } else continue; for(i=n;i>=1;i--) { if(adj[pop][i]==1&&visited[i]==0) { top++; stack[top]=i; } } } } void bfs(int v) { int i,front,rear; int que[50]; front=rear=-1; printf("%d ",v); visited[v]=1; rear++; front++; que[rear]=v; while(front<=rear) { v=que[front]; front++; for (i=1;i<=n;i++) { if (adj[v][i]==1&&visited[i]==0) { printf("%d ",i); visited[i]=1; rear++; que[rear]=i; } } } }
No comments:
Post a Comment