Aim:

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

Solution :

C program to implement the Breadth First Search a graph traversal methods

#include<stdio.h>

// creating queue data structure using arrays
int queue[10];

// defining pointers of the queue to perform pop and push
int front=0,back=0;

// defining push operation on the queue
void push(int var)
{
    queue[back] = var;
    back++;
}

// defining pop operation on queue
void pop()
{
    queue[front] = 0;
    front++;
}

// creating a visited array to keep the track of visited nodes
int visited[7] = {0};

int main()
{
    int v,n,i,j;
    // adjacenty matrix representing graph
    int graph[10][10];
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    printf("Enter graph data in matrix form:    \n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &graph[i][j]);

    // adding a starting node in the list 
    printf("Enter the starting vertex: ");
    scanf("%d", &v);
    push(v);
    while(front != back)
    {
        int current = queue[front];
        
        // printing current element 
        printf("%d ", current);
        
        // popping the front element from the queue
        pop();
 
        for(int i=0;i < 6;i++)
        {
            // adding non-visited connected nodes of the current node to the queue 
            if((graph[current-1][i] == 1) && (visited[i] == 0))
            {
                visited[i] = 1; // marking visisted
                push(i+1);
            }
        }
    }
    return 0;
}

Enter the number of vertices: 6
Enter graph data in matrix form:    
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0
Enter the starting vertex: 2
2 1 3 2 4 5 6 

Related Content :

Data Structures Lab Programs

1) Write a program that uses functions to perform the following operations on singly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

2) Write a program that uses functions to perform the following operations on doubly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

3) Write a program that uses functions to perform the following operations on circular linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

4) Write a program that implement Stack (its operations) using Array View Solution

5) Write a program that implement Stack (its operations) using Linked List (Pointer) View Solution

6) Write a program that implement Queue(its operations) using Array View Solution

7) Write a program that implement Queue (its operations) using Linked List (Pointer) View Solution

8) Write a program that implements Quick sort sorting methods to sort a given list of integers in ascending order View Solution

9) Write a program that implements Merge sort sorting methods to sort a given list of integers in ascending order View Solution

10) Write a program that implements Heap sort sorting methods to sort a given list of integers in ascending order View Solution

11) Write a program to implement the tree traversal methods using Recursive View Solution

12) Write a program to implement the tree traversal methods using Non Recursive View Solution

13) Write a program to implement Binary Search Tree (its operations) View Solution

14) Write a program to implement AVL Tree (its operations) View Solution

15) Write a program to implement Red - Black Tree (its operations) View Solution

16) Write a program to implement B Trees (its operations) View Solution

17) Write a program to implement B+ Trees (its operations) View Solution

18) Write a program to implement the graph traversal methods (Breadth First Search) View Solution

19) Write a program to implement the graph traversal methods (Depth First Search) View Solution

20) Write a program to Implement a Pattern matching algorithms using Boyer- Moore View Solution

21) Write a program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt View Solution