Graph using adjacency Matrix with BFS and DFS traversals.

 Aim

To implement a Graph using Adjacency Matrix and perform Breadth First Search (BFS) and Depth First Search (DFS) traversals.

Objective

  1. Represent a graph using Adjacency Matrix.

  2. Perform BFS traversal using a queue.

  3. Perform DFS traversal using recursion (stack concept).

  4. Understand the difference between BFS and DFS in exploring nodes.

Algorithm

1. Graph Representation

  1. Start

  2. Initialize adj[n][n] to 0 (no edges).

  3. For each edge (u, v), set adj[u][v] = 1 and adj[v][u] = 1 (for undirected graph).

  4. End.

2. BFS Traversal

  1. Start

  2. Mark the starting vertex as visited and insert into queue.

  3. Repeat until queue is empty:

    • Dequeue a vertex u and print it.

    • For each adjacent vertex v of u, if not visited, mark visited and enqueue it.

  4. End.

3. DFS Traversal

  1. Start

  2. Mark the current vertex as visited and print it.

  3. For each adjacent vertex v of current node:

    • If v is not visited, recursively call DFS on v.

  4. End.

Flowchart

Generated image

C Program: Graph using Adjacency Matrix with BFS and DFS

#include <stdio.h>

#include <stdlib.h>

#define MAX 10

int adj[MAX][MAX];   // adjacency matrix

int visited[MAX];    // visited array for DFS & BFS

int queue[MAX];      // queue for BFS

int front = -1, rear = -1;

// Function to add edge

void addEdge(int u, int v) {

    adj[u][v] = 1;

    adj[v][u] = 1;   // For undirected graph

}

// BFS traversal

void bfs(int start, int n) {

    int i;

    front = rear = 0;

    queue[rear] = start;

    visited[start] = 1;

    printf("BFS Traversal: ");

    while (front <= rear) {

        int node = queue[front++];

        printf("%d ", node);

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

            if (adj[node][i] == 1 && visited[i] == 0) {

                queue[++rear] = i;

                visited[i] = 1;

            }

        }

    }

    printf("\n");

}

// DFS traversal

void dfs(int start, int n) {

    int i;

    printf("%d ", start);

    visited[start] = 1;

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

        if (adj[start][i] == 1 && visited[i] == 0) {

            dfs(i, n);

        }

    }

}

int main() {

    int n, e, i, u, v, start;

    printf("Enter number of vertices: ");

    scanf("%d", &n);

    // Initialize adjacency matrix

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

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

            adj[i][j] = 0;

        }

    }

    printf("Enter number of edges: ");

    scanf("%d", &e);

    printf("Enter edges (u v):\n");

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

        scanf("%d%d", &u, &v);

        addEdge(u, v);

    }

    printf("Enter starting vertex: ");

    scanf("%d", &start);

    // BFS

    for (i = 0; i < n; i++) visited[i] = 0;

    bfs(start, n);

    // DFS

    for (i = 0; i < n; i++) visited[i] = 0;

    printf("DFS Traversal: ");

    dfs(start, n);

    printf("\n");

    return 0;

}

Comments

Post a Comment

Popular posts from this blog

Stack using array

Image
  1) Stack using Array Aim To implement stack operations (Push, Pop, Display) using arrays in C. Objective To study the LIFO (Last In, First Out) principle. To practice array-based implementation of data structures. Algorithm Push: If top == n-1, then overflow. Else top = top + 1 and insert element at stack[top]. Pop: If top == -1, then underflow. Else delete element from stack[top], then top = top - 1. Display: If top == -1, stack empty. Else print elements from stack[top] to stack[0]. Flowchart  C Code (Stack using Array) #include <stdio.h> #define MAX 5 int main() {     int stack[MAX], top = -1, choice, item, i;     while (1) {         printf("\n--- Stack Menu ---\n");         printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");         printf("Enter choice: ");         scan...
Read more

Bubble Sort

Image
  2) Bubble Sort Aim To arrange elements in ascending order using Bubble Sort (without functions). Objective To study simple comparison-based sorting. To understand swapping of adjacent elements. Algorithm Input number of elements and array. Repeat for i = 0 to n-1 Repeat for j = 0 to n-i-2 If arr[j] > arr[j+1], swap them. Print sorted array. Flowchart C Code #include <stdio.h> int main() {     int n, i, j, temp;     printf("Enter number of elements: ");     scanf("%d", &n);     int arr[n];     printf("Enter array elements: ");     for (i = 0; i < n; i++)         scanf("%d", &arr[i]);     for (i = 0; i < n - 1; i++) {         for (j = 0; j < n - i - 1; j++) {             if (arr[j]...
Read more

Singly linked list implementation

Image
  Singly Linked List Implementation Aim To implement basic operations on a Singly Linked List in C. Objective To study dynamic memory allocation using linked lists. To perform Insert, Delete, Traverse operations. To understand pointer manipulation in data structures. Operations in Singly Linked List Insert at Beginning Insert at End Insert at Position Delete from Beginning Delete from End Delete from Position Display List Algorithm Insert at Beginning Create new node. new->next = head. head = new. Insert at End Create new node. If list empty → head = new. Else traverse to last node, set last->next = new. Insert at Position Traverse until position-1. Link new node in between. Delete from Beginning If empty → print "Underflow". Else move head to head->next, free old head. Delete from End If empty → print "Underflow". Else traverse to last-1 node, set last->next = NULL, free last. Delete from Position Traverse until position-1. Adjust links and free node...
Read more