C Program to Implement Depth-First Search (DFS)

Introduction

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root (or an arbitrary node in the case of a graph) and explores as far as possible along each branch before backtracking. DFS can be implemented using recursion (implicitly using a stack) or using an explicit stack data structure.

Example:

• Graph Structure:

  1 - 2
  |   |
  3 - 4
  

• DFS Output starting from Node 1: 1 2 4 3

Problem Statement

Create a C program that:

• Implements the Depth-First Search algorithm for a graph.
• Traverses the graph using DFS and outputs the nodes in the order they are visited.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output and memory allocation functions.
2. Define the Structure for the Graph: Use an adjacency list to represent the graph.
3. Implement the DFS Function: This function will traverse the graph using DFS starting from a given node.
4. Create a Main Function: Build a sample graph and perform DFS traversal.

C Program to Implement Depth-First Search (DFS)

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

// Structure to represent an adjacency list node
struct Node {
    int vertex;
    struct Node* next;
};

// Structure to represent an adjacency list
struct AdjList {
    struct Node* head;
};

// Structure to represent a graph
struct Graph {
    int numVertices;
    struct AdjList* array;
    bool* visited;
};

// Function to create a new adjacency list node
struct Node* createNode(int vertex) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    // Create an array of adjacency lists. Size of array will be numVertices
    graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));
    graph->visited = (bool*)malloc(vertices * sizeof(bool));

    for (int i = 0; i < vertices; i++) {
        graph->array[i].head = NULL;
        graph->visited[i] = false;
    }

    return graph;
}

// Function to add an edge to the graph (undirected graph)
void addEdge(struct Graph* graph, int src, int dest) {
    // Add an edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since the graph is undirected, add an edge from dest to src as well
    newNode = createNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to perform DFS traversal
void dfs(struct Graph* graph, int vertex) {
    struct Node* adjList = graph->array[vertex].head;
    struct Node* temp = adjList;

    graph->visited[vertex] = true;
    printf("%d ", vertex);

    while (temp != NULL) {
        int connectedVertex = temp->vertex;

        if (!graph->visited[connectedVertex]) {
            dfs(graph, connectedVertex);
        }
        temp = temp->next;
    }
}

int main() {
    int vertices = 4;

    // Create a graph with 4 vertices
    struct Graph* graph = createGraph(vertices);

    // Add edges
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    // Perform DFS traversal starting from vertex 0
    printf("Depth-First Search starting from vertex 0:\n");
    dfs(graph, 0);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Structure for the Adjacency List Node

• The struct Node defines a node in the adjacency list, representing an edge from one vertex to another.

Structure for the Graph

• The struct Graph represents the graph using an array of adjacency lists, where each list corresponds to a vertex and contains all vertices connected to it.
• The graph also maintains an array visited to keep track of visited vertices during DFS.

Function to Create a Graph

• The createGraph function initializes the graph’s adjacency lists and the visited array for the specified number of vertices.

Function to Add an Edge

• The addEdge function adds an edge between two vertices in an undirected graph by updating the adjacency lists of both vertices.

Function to Perform DFS Traversal

• The dfs function performs DFS starting from the specified vertex. It marks the vertex as visited, prints it, and recursively visits all its adjacent vertices that have not yet been visited.

Main Function

• The main function creates a sample graph with 4 vertices, adds edges, and then performs DFS starting from vertex 0.

Output Example

Example Output:

Depth-First Search starting from vertex 0:
0 2 3 1

Example Output (Different Graph):

If the graph is modified, for example:

Graph Structure:
0 - 1
|   |
2 - 3

The DFS traversal starting from vertex 0 could output:

Depth-First Search starting from vertex 0:
0 1 3 2

Conclusion

This C program demonstrates how to implement Depth-First Search (DFS) for a graph using an adjacency list. DFS is a fundamental graph traversal algorithm widely used for searching, exploring graphs, and solving problems such as connected components, topological sorting, and more. This program provides a practical example of how DFS can be implemented and applied in C programming.