#include<conio.h> #include<stdio.h> #include<stdlib.h> #define MAX 20 typedef struct Q { int data[MAX]; int R,F; }Q; typedef struct node { struct node *next; int vertex; }node; void enqueue(Q *,int); int dequque(Q *); int empty(Q *); int full(Q *); void BFS(int); void readgraph(); //create an adjecency list void insert(int vi,int vj); //insert an edge (vi,vj)in adj.list void DFS(int i); int visited[MAX]; node *G[20]; //heads of the linked list int n; // no of nodes void main() { int i,op; clrscr(); do { printf("\n\n1)Create\n2)BFS\n3)DFS\n4)Quit"); printf("\nEnter Your Choice: "); scanf("%d",&op); switch(op) { case 1: readgraph();break; case 2: printf("\nStarting Node No. : "); scanf("%d",&i); BFS(i);break; case 3: for(i=0;i<n;i++) visited[i]=0; printf("\nStarting Node No. : "); scanf("%d",&i); DFS(i);break; } }while(op!=4); } void BFS(int v) { int w,i,visited[MAX]; Q q; node *p; q.R=q.F=-1; //initialise for(i=0;i<n;i++) visited[i]=0; enqueue(&q,v); printf("\nVisit\t%d",v); visited[v]=1; while(!empty(&q)) { v=dequeue(&q); //insert all unvisited,adjacent vertices of v into queue for(p=G[v];p!=NULL;p=p->next) { w=p->vertex; if(visited[w]==0) { enqueue(&q,w); visited[w]=1; printf("\nvisit\t%d",w); } } } } void DFS(int i) { node *p; printf("\n%d",i); p=G[i]; visited[i]=1; while(p!=NULL) { i=p->vertex; if(!visited[i]) DFS(i); p=p->next; } } int empty(Q *P) { if(P->R==-1) return(1); return(0); } int full(Q *P) { if(P->R==MAX-1) return(1); return(0); } void enqueue(Q *P,int x) { if(P->R==-1) { P->R=P->F=0; P->data[P->R]=x; } else { P->R=P->R+1; P->data[P->R]=x; } } int dequeue(Q *P) { int x; x=P->data[P->F]; if(P->R==P->F) { P->R=-1; P->F=-1; } else P->F=P->F+1; return(x); } void readgraph() { int i,vi,vj,no_of_edges; printf("\nEnter no. of vertices :"); scanf("%d",&n); //initialise G[] with NULL for(i=0;i<n;i++) G[i]=NULL; //read edges and insert them in G[] printf("\nEnter no of edges :"); scanf("%d",&no_of_edges); for(i=0;i<no_of_edges;i++) { printf("\nEnter an edge (u,v) :"); scanf("%d%d",&vi,&vj); insert(vi,vj); insert(vj,vi); } } void insert(int vi,int vj) { node *p,*q; //acquire memory for the new node q=(node *)malloc(sizeof(node)); q->vertex=vj; q->next=NULL; //insert the node in the linked list for the vertex no. vi if(G[vi]==NULL) G[vi]=q; else { // go to the end of linked list p=G[vi]; while(p->next!=NULL) p=p->next; p->next=q; } }
OUTPUT:-
1)Create 2)BFS 3)DFS 4)Quit Enter Your Choice: 1 Enter no. of vertices :4 Enter no of edges :5 Enter an edge (u,v) :1 2 Enter an edge (u,v) :2 3 Enter an edge (u,v) :3 4 Enter an edge (u,v) :4 1 Enter an edge (u,v) :1 3 1)Create 2)BFS 3)DFS 4)Quit Enter Your Choice: 2 Starting Node No. : 1 Visit 1 visit 2 visit 3 visit 4 1)Create 2)BFS 3)DFS 4)Quit Enter Your Choice: 3 Starting Node No. :2 2 1 4 3 1)Create 2)BFS 3)DFS 4)Quit Enter Your Choice: 2 Starting Node No. : 4 Visit 4 visit 3 visit 1 visit 2 1)Create 2)BFS 3)DFS 4)Quit Enter Your Choice: 4
erroneous
ReplyDeleteThere is an error on BFS initialization, it should be:
ReplyDeletefor(i=0;i <=n; i++)
visited[i]=0;
These are the great blogs; I assure you that I really enjoyed a lot in reading.
ReplyDeletec++ programming tutorial