Bfs.docx
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Bfs.docx as PDF for free.
More details
- Words: 157
- Pages: 2
/*Breadth First Search Traversal of a Graph */ #include<stdio.h> #include void bfs(int v); int n,a[10][10],status[10],front=-1,rear=-1,size=10,queue[20]; void insert(int); int delet(); void main() { int i,j,v; clrscr(); printf("Enter the no. of nodes in the graph\n"); scanf("%d",&n); printf("Enter the adjacency matrix \n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&a[i][j]); } } printf("The adjacency matrix shown as\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%d\t",a[i][j]); } printf("\n"); } printf("Enter the starting node for Breadth First search\n"); scanf("%d",&v); //Make every node as ready state for(i=1;i<=n;i++) status[i]=1; bfs(v); getch(); } void bfs(int v) { int deleted,i,count=0; insert(v); while(front!= -1) { deleted=delet(); if(status[deleted]==2)
{ printf("%d\t",deleted); status[deleted]=3; count++; } for(i=n;i>=1;i--) { if(a[deleted][i]==1 && status[i]==1) { /*insert all the unvisited neighbours in the queue*/ insert(i); } } } if(count!=n) printf("\nGraph is not connected"); } void insert(int vertex) { if(rear==size-1) printf("Queue is over flow"); else { rear=rear+1; queue[rear]=vertex; status[vertex]=2; if(front==-1) front++; } } int delet() { int x; if(front==-1) return -1; else if(front==rear) { x=queue[front]; front=rear=-1; } else x=queue[front++]; return x; }
{ printf("%d\t",deleted); status[deleted]=3; count++; } for(i=n;i>=1;i--) { if(a[deleted][i]==1 && status[i]==1) { /*insert all the unvisited neighbours in the queue*/ insert(i); } } } if(count!=n) printf("\nGraph is not connected"); } void insert(int vertex) { if(rear==size-1) printf("Queue is over flow"); else { rear=rear+1; queue[rear]=vertex; status[vertex]=2; if(front==-1) front++; } } int delet() { int x; if(front==-1) return -1; else if(front==rear) { x=queue[front]; front=rear=-1; } else x=queue[front++]; return x; }
More Documents from "Parameswara Rao"
Half Converter Rload 1.pdf
May 2020 2
Bfs.docx
May 2020 2
Discoverer Implementation
June 2020 14
Oracle Discoverer Applications
June 2020 13
Discoverer Case Study
June 2020 17