Graph Traversal - DFS

Write a C program for finding the Depth First Search of a graph.

//C program for finding the Depth First Search of a graph. 

#include <stdio.h>

#define MAX_VERTICES 100

// Function to perform Depth-First Search (DFS) traversal

void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int visited[MAX_VERTICES], int vertices, int start) {

    int i;

    printf(" %d --> ", start); // Print the current vertex

    visited[start] = 1;    // Mark the current vertex as visited

    // Visit all adjacent vertices

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

        if (graph[start][i] == 1 && !visited[i]) {

            DFS(graph, visited, vertices, i);

        }

    }

}

// Function to print the adjacency matrix

void printAdjacencyMatrix(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {

    int i, j;

    printf("Adjacency Matrix:\n");

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

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

            printf("%d ", graph[i][j]);

        }

        printf("\n");

    }

}

int main() {

    int vertices, edges, i, j;

    printf("\n****Depth-First Search (DFS) traversal****\n");

    printf("-----------------------------------------------\n");

    // Input the number of vertices

    printf("Enter the number of vertices: ");

    scanf("%d", &vertices);

    if (vertices <= 0 || vertices > MAX_VERTICES) {

        printf("Invalid number of vertices. Exiting...\n");

        return 1;

    }

    int graph[MAX_VERTICES][MAX_VERTICES] = {0}; // Initialize the adjacency matrix with zeros

    int visited[MAX_VERTICES] = {0};             // Initialize the visited array with zeros

    // Input the number of edges

    printf("Enter the number of edges: ");

    scanf("%d", &edges);

    if (edges < 0 || edges > vertices * (vertices - 1)) {

        printf("Invalid number of edges. Exiting...\n");

        return 1;

    }

    // Input edges and construct the adjacency matrix

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

        int start, end;

        printf("Enter edge %d (start end): ", i + 1);

        scanf("%d %d", &start, &end);

        // Validate input vertices

        if (start < 0 || start >= vertices || end < 0 || end >= vertices) {

            printf("Invalid vertices. Try again.\n");

            i--;

            continue;

        }

        graph[start][end] = 1;

        // For directed graph, comment the following line:

        graph[end][start] = 1;

    }

    // Print the adjacency matrix

    printAdjacencyMatrix(graph, vertices);

    // Input the starting vertex for DFS traversal

    int startVertex;

    printf("Enter the starting vertex for DFS traversal: ");

    scanf("%d", &startVertex);

    if (startVertex < 0 || startVertex >= vertices) {

        printf("Invalid starting vertex. Exiting...\n");

        return 1;

    }

    printf("DFS Traversal Order: ");

    DFS(graph, visited, vertices, startVertex);

    return 0;

}

Input/Output: