Program for DFS traversal in Graph

C Program to implement Graph Structure: Exercise-4 with Solution

Write a C program that implements DFS (Depth-First Search) traversal for a graph in C. Print the order of visited vertices.

From Wikipedia -

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

Animated example of a depth-first search:

Source: Wikipedia

Sample Solution:

C Code:

#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) {
    printf("%d ", start); // Print the current vertex
    visited[start] = 1;    // Mark the current vertex as visited

    // Visit all adjacent vertices
    for (int i = 0; i < vertices; i++) {
        if (graph[start][i] == 1 && !visited[i]) {
            DFS(graph, visited, vertices, i);
        }
    }
}

int main() {
    int vertices, edges;

    // 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 (int 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 undirected graph, uncomment the following line:
        // graph[end][start] = 1;
    }

    // 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;
}

Output:

Enter the number of vertices: 5
Enter the number of edges: 6
Enter edge 1 (start end): 0 1
Enter edge 2 (start end): 1 2
Enter edge 3 (start end): 2 3
Enter edge 4 (start end): 3 4
Enter edge 5 (start end): 4 0
Enter edge 6 (start end): 2 4
Enter the starting vertex for DFS traversal: 2
DFS Traversal Order: 2 3 4 0 1

Explanation:

The above C exercises perform Depth-First Search (DFS) traversal on a graph represented by an adjacency matrix. Here's a brief explanation:

• DFS Function:
• The "DFS()" function takes the graph, an array to track visited vertices, the total number of vertices, and the starting vertex as parameters.
• It prints the current vertex, marks it as visited, and then recursively explores all unvisited adjacent vertices.
• Main Function:
• It takes user input for the number of vertices and edges.
• Constructs the adjacency matrix based on user input for edges.
• Takes the starting vertex for DFS traversal.
• Calls the "DFS()" function with the provided parameters.
• Outputs the DFS traversal order.
• User Input:
• The user is prompted to input the number of vertices and edges.
• For each edge, the user inputs the starting and ending vertices.
• Output:
• The program outputs the DFS traversal order starting at the specified vertex.

Flowchart:

C Programming Code Editor:

Previous: C Program to add directed edge in Graph.
Next: Breadth-First Search (BFS) Traversal in Graph: C Program Example.