C DFS (Depth-First Search) 🎯

Welcome to the exciting world of Depth-First Search (DFS) in C programming! In this lesson, we'll dive deep into understanding DFS, its applications, and how to implement it with practical examples. Let's get started!

Understanding Depth-First Search (DFS) 📝

DFS is a popular algorithm used for traversing or searching tree or graph structures. It explores as far as possible along each path before backtracking.

Why DFS? 💡

DFS is a useful algorithm for solving graph-related problems, like finding connected components, cycles, shortest paths, etc.
DFS is a recursive algorithm, which makes it easy to implement and understand.

DFS Algorithm Steps 📝

Start at the root node.
Mark the current node as visited.
Explore the adjacent nodes recursively.
If no more adjacent nodes are available, backtrack to the previous node.
Repeat steps 2-4 until all nodes have been visited.

Data Structures Required 📝

int visited[n]: To keep track of visited nodes.
adjacencyList[n][n] or adjacencyMatrix[n][n]: To store the graph data.

DFS Algorithm in C - Recursive Implementation 💡

#include<stdio.h>

#define maxVertices 100

void DFSUtil(int vertex, int visited[], int adjacencyMatrix[maxVertices][maxVertices]) {
    visited[vertex] = 1;
    printf("Visiting vertex: %d\n", vertex);

    for (int i = 0; i < maxVertices; i++) {
        if (adjacencyMatrix[vertex][i] == 1 && visited[i] == 0)
            DFSUtil(i, visited, adjacencyMatrix);
    }
}

void DFS(int adjacencyMatrix[maxVertices][maxVertices], int n) {
    int visited[maxVertices];

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

    for (int i = 0; i < n; i++) {
        if (visited[i] == 0)
            DFSUtil(i, visited, adjacencyMatrix);
    }
}

DFS Algorithm in C - Iterative Implementation 💡

Although DFS is inherently recursive, it can also be implemented iteratively using a stack.

#include<stdio.h>
#include<stack>

#define maxVertices 100

void DFSUtil(int vertex, int visited[], int adjacencyList[maxVertices][maxVertices]) {
    std::stack<int> stack;

    visited[vertex] = 1;
    printf("Visiting vertex: %d\n", vertex);
    stack.push(vertex);

    while (!stack.empty()) {
        int currentVertex = stack.top();
        stack.pop();

        for (int i = 0; i < maxVertices; i++) {
            if (adjacencyList[currentVertex][i] == 1 && visited[i] == 0) {
                stack.push(currentVertex);
                visited[i] = 1;
                printf("Visiting vertex: %d\n", i);
                stack.push(i);
                break;
            }
        }
    }
}

void DFS(int adjacencyList[maxVertices][maxVertices], int n) {
    int visited[maxVertices];

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

    for (int i = 0; i < n; i++) {
        if (visited[i] == 0)
            DFSUtil(i, visited, adjacencyList);
    }
}

Practical Application 💡

DFS can be used to find connected components in an undirected graph or check if a graph contains a cycle.

:::quiz Question: Which of the following options correctly defines the function to perform DFS using the iterative approach in C?

A: void DFSUtil(int, int[], int[][]) B: void DFSUtil(int*, int[], int[][]) C: void DFSUtil(int, int[], int[][])

Correct: C Explanation: The function definition should use int for the data type of the vertex, as ints are more suitable for graph traversal. Additionally, the standard function prototype in C includes the data type of the parameter.