Implementing Merge Sort, BFS, and DFS Algorithms in C

Posted on Oct 30, 2025 in Computer Engineering in Computer Engineering

Fundamental Algorithms in C Programming

This document provides C implementations for three core algorithms: Merge Sort for efficient sorting, and Breadth-First Search (BFS) and Depth-First Search (DFS) for graph traversal.

1. Merge Sort Implementation

Merge Sort is a divide-and-conquer algorithm. The following code demonstrates the recursive sorting function and the main driver program. (Note: The required merge function definition is assumed but not included in this snippet.)

Merge Sort Recursive Function

void mergesort(int a[], int low, int high)
{
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        mergesort(a, low, mid);
        mergesort(a, mid + 1, high);
        merge(a, mid, low, high); // Assumes merge function exists
    }
}

Utility and Main Function for Merge Sort

void printarray(int a[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
}

int main() {
    int n, i;
    printf("Enter n: ");
    scanf("%d", &n);
    int a[n];
    printf("Enter elements:\n");
    
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    
    printf("Input array: ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    
    mergesort(a, 0, n - 1);
    printf("\nSorted array: ");
    printarray(a, n);
    
    return 0;
}

2. Graph Traversal: BFS and DFS

This section implements Breadth-First Search (BFS) and Depth-First Search (DFS) for graph traversal using an adjacency matrix representation. BFS utilizes a linked-list based queue structure.

Required Headers and Global Variables

#include <stdio.h>
#include <stdlib.h>

struct queue {
    int data;
    struct queue *next;
};

struct queue* front = NULL;
struct queue* rear = NULL;
int n; // Global variable for the number of vertices

Queue Operations for BFS

Enqueue Function

void enqueue(int data) {
    struct queue *newnode = (struct queue*)malloc(sizeof(struct queue));
    newnode->data = data;
    newnode->next = NULL;
    if (front == NULL && rear == NULL) {
        front = rear = newnode;
    } else {
        rear->next = newnode;
        rear = newnode;
    }
}

Dequeue Function

int dequeue() {
    int var = -1;
    if (front == NULL && rear == NULL) {
        printf("Queue is empty\n");
    } else {
        struct queue *temp = front;
        front = front->next;
        var = temp->data;
        free(temp);
    }
    return var;
}

Breadth-First Search (BFS) Implementation

void bfs(int start, int arr[n][n]) {
    int visited[n];
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    enqueue(start);
    visited[start] = 1;
    
    printf("BFS Traversal: ");
    while (front != NULL) {
        for (int i = 0; i < n; i++) {
            // Check adjacency and unvisited status
            if (arr[front->data][i] != 0 && visited[i] == 0) {
                enqueue(i);
                visited[i] = 1;
            }
        }
        int ver = dequeue();
        printf("%d ", ver);
    }
    printf("\n");
}

Depth-First Search (DFS) Implementation

void dfs(int node, int arr[n][n], int visited[n]) {
    printf("%d ", node);
    visited[node] = 1;
    for (int i = 0; i < n; i++) {
        // Check adjacency and unvisited status
        if (arr[node][i] != 0 && visited[i] == 0) {
            dfs(i, arr, visited);
        }
    }
}

Graph Initialization Function

void graph(int arr[n][n]) {
    int i, j, val, value;
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            printf("Enter whether edge is present between vertices %d -- %d (1-yes | 0-no): ", i, j);
            scanf("%d", &val);
            if (val == 1) {
                printf("Enter edge value: ");
                scanf("%d", &value);
                arr[i][j] = value;
                arr[j][i] = value; // Undirected graph
            } else {
                arr[i][j] = 0;
                arr[j][i] = 0;
            }
        }
    }

    printf("\nAdjacency Matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

Main Driver for Graph Traversal

int main() {
    int start;
    int node;
    int ans;
    
    printf("Enter number of vertices in the graph: ");
    scanf("%d", &n);
    int arr[n][n];
    graph(arr);
    
    do {
        printf("\n--- BFS ---\n");
        printf("Enter starting node for BFS: ");
        scanf("%d", &start);
        bfs(start, arr);

        // Initialize visited array for DFS
        int visited[n];
        for (int i = 0; i < n; i++) {
            visited[i] = 0;
        }
        
        printf("\n--- DFS ---\n");
        printf("Enter starting node for DFS: ");
        scanf("%d", &node);
        printf("DFS Traversal: ");
        dfs(node, arr, visited);
        printf("\n");
        
        printf("Do you want to continue? (1-yes | 0-no): ");
        scanf("%d", &ans);
    } while (ans == 1);

    return 0;
}