Notice: Undefined index: url2 in /home/u681245571/domains/studyglance.in/public_html/labprograms/dsdisplay.php on line 83

Notice: Undefined index: url3 in /home/u681245571/domains/studyglance.in/public_html/labprograms/dsdisplay.php on line 84

Notice: Undefined index: url4 in /home/u681245571/domains/studyglance.in/public_html/labprograms/dsdisplay.php on line 85

Notice: Undefined index: opurl2 in /home/u681245571/domains/studyglance.in/public_html/labprograms/dsdisplay.php on line 88

Notice: Undefined index: opurl3 in /home/u681245571/domains/studyglance.in/public_html/labprograms/dsdisplay.php on line 89

Notice: Undefined index: opurl4 in /home/u681245571/domains/studyglance.in/public_html/labprograms/dsdisplay.php on line 90

[R18] Data Structures Lab Manual [ Lab Programs ]

---

Aim:

Write a program to implement Breadth First Search (BFS) graph traversal methods.

Source Code:

bfs.c

#include <stdio.h>



#define QUEUE_SIZE 20

#define MAX 20



//queue

int queue[QUEUE_SIZE];

int queue_front, queue_end;

void enqueue(int v);

int dequeue();



void bfs(int Adj[MAX][MAX], int n, int source);



int main(void) {

//Adj matrix

int Adj[MAX][MAX] ;//= {{0,1,0,0},{0,0,0,1},{1,0,0,0},{1,0,1,0}};//    {0,1,0,0},    {0,1,1,1},    {1,0,0,1},    {0,0,1,0}  };



int i,j,n;// = 4;  //no. of vertex

int starting_vertex ;//= 2;

printf("enter no of vertex");

scanf("%d",&n);

printf("\n enter %d vertices into matrix",n);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

scanf("%d",&Adj[i][j]);

printf("\nenter starting vertex");

scanf("%d",&starting_vertex);



bfs(Adj, n, starting_vertex);



return 0;

}



void bfs(int Adj[MAX][MAX], int n, int source) {

//variables

int i, j;



//visited array to flag the vertex that

//were visited

int visited[MAX];



//queue

queue_front = 0;

queue_end = 0;



//set visited for all vertex to 0 (means unvisited)

for(i = 0; i <= MAX; i++) {

visited[i] = 0;

}



//mark the visited source

visited[source] = 1;



//enqueue visited vertex

enqueue(source);



//print the vertex as result

printf("%d ", source);



//continue till queue is not empty

while(queue_front <= queue_end) {

//dequeue first element from the queue

i = dequeue();



for(j = 0; j <n; j++) {

if(visited[j] == 0 && Adj[i][j] == 1) {

//mark vertex as visited

visited[j] = 1;



//push vertex into stack

enqueue(j);



//print the vertex as result

printf("%d ", j);

}

}

}

printf("\n");

}



void enqueue(int v) {

queue[queue_end] = v;

queue_end++;

}



int dequeue() {

int index = queue_front;

queue_front++;

return queue[index];

}

Output:

---

Related Content :

Data Structures Lab Programs

1) Write a C program that uses functions to perform the following on Singly Linked List: 
i) Creation    
ii) Insertion   
iii) Deletion   
iv) Traversal   

View Solution

2) Write a program that uses functions to perform the following operations on Doubly Linked List.:
i) Creation    
ii) Insertion    
iii) Deletion    
iv) Traversal    

View Solution

3) Write a program that uses functions to perform the following operations on Circular Linked List.:
i) Creation     
ii) Insertion    
iii) Deletion    
iv) Traversal   

View Solution

4) Write a program that implement Stack (its operations) using Arrays                    

View Solution

5) Write a program that implement Stack (its operations) using Pointers   

View Solution

6) Write a program that implement Queue (its operations) using Arrays            

View Solution

7) Write a program that implement Queue (its operations) using Pointers   

View Solution

8) Write a program that implements Bubble Sort Method to sort a given list of integers in ascending order.

View Solution

9) Write a program that implements Selection Sort Method to sort a given list of integers in ascending order.

View Solution

10) Write a program that implements Insertion Sort Method to sort a given list of integers in ascending order.

View Solution

11) Write a program that use both recursive and non recursive functions to perform Linear search operations for a Key value in a given list of integers.

View Solution

12) Write a program that use both recursive and non recursive functions to perform Binary search operations for a Key value in a given list of integers.

View Solution

13) Write a program to implement the tree traversal methods.

View Solution

14) Write a program to implement Depth First Search (DFS) graph traversal methods.

View Solution

15) Write a program to implement Breadth First Search (BFS) graph traversal methods.

View Solution

---