Depth First Search (DFS) in C

Introduction

Depth First Search (DFS) is a fundamental but important algorithm that is used in graph theory to explore nodes & edges of a graph. It's like walking through a maze, where you go as deep as you can down one path before you turn back to try another. In computer science, DFS is important for solving problems like figuring out network connections, solving puzzles, or finding ways through maps.

In this article, we will learn about the working of DFS, its pseudocode, algorithm, implementation in C, examples, time & space complexity, & applications.

What is Depth First Search (DFS) in C?

Depth First Search (DFS) in C is an algorithm used to traverse or search a graph or tree. It explores as far down a branch as possible before backtracking. DFS uses a stack (either explicit or recursive) to visit nodes, ensuring all vertices are explored systematically in depth-first order.

How does DFS work?

Depth-First Search (DFS) is an algorithm for traversing a tree or graph data structure. It starts at the root node & explores as far as possible along each branch before backtracking.

The basic idea behind DFS is to explore deeper into the data structure before exploring the next sibling node. It uses a stack data structure to keep track of the nodes to be visited next.

Let’s see how the DFS algorithm works:

1. Start by putting the root node in the stack.

2. Take the top item of the stack & add it to the visited list.

3. Create a list of that node's adjacent nodes. Add those nodes to the top of the stack.

4. Keep repeating steps 2 & 3 until the stack is empty.

The algorithm traverses each branch completely before moving on to the next branch. This process continues until all the nodes are visited.

Note: DFS can be implemented with the help of recursion or iteration. The recursive method goes deep into one path first before checking others. The iterative method, on the other hand, uses a stack to remember which places it needs to visit next.

DFS Pseudocode

The pseudocode for the Depth-First Search (DFS) algorithm is:

DFS(node)
    if node is NULL
        return
    mark node as visited
    print node value
    for each unvisited adjacent node of current node
        DFS(adjacent node)

Now, let's understand what this pseudocode means:

1. The DFS function takes a node as input.

2. If the node is NULL, return as there is nothing to traverse.

3. Mark the current node as visited to avoid revisiting it.

4. Print the value of the current node.

5. For each unvisited adjacent node of the current node:

- Recursively call the DFS function with the adjacent node as input.

The pseudocode follows the recursive approach for implementing DFS. It starts with a given node, marks it as visited, prints its value, & then recursively calls the DFS function for each unvisited adjacent node.

Depth First Search Algorithm

Now, we know what DFS algorithm is and why it is important, let’s discuss how DFS algorithm could be implemented :

1. Begin at the root node of the graph or tree.

2. Mark the current node as visited.

3. Print the value of the current node.

4. For each unvisited adjacent node of the current node:

- Recursively call the DFS function with the adjacent node as input.

5. If all adjacent nodes have been visited or there are no more adjacent nodes, backtrack to the previous node.

6. Repeat steps 2-5 until all nodes have been visited.

The DFS algorithm follows a specific order of traversal:

- Visit the current node.

- Explore the first adjacent unvisited node by recursively calling DFS on it.

- If there are no more unvisited adjacent nodes, backtrack to the previous node.

- Repeat the process until all nodes have been visited.

Note: The DFS algorithm can be implemented using recursion or iteration using a stack data structure. The recursive implementation is more straightforward & easier to understand, while the iterative implementation can be more efficient in terms of space complexity.

DFS Implementation in C

Now, let's see how to implement the Depth First Search (DFS) algorithm in C. We'll use an adjacency list representation of a graph & implement DFS using recursion.

The code for the DFS implementation in C is :

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

#define MAX_VERTICES 100

// Graph node
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;


// Graph
typedef struct Graph {
    int numVertices;
    Node* adjList[MAX_VERTICES];
    int visited[MAX_VERTICES];
} Graph;


// Create a new node
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

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


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

    return graph;
}


// Add an edge to the graph
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;


    newNode = createNode(src);
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}


// DFS traversal
void DFS(Graph* graph, int vertex) {
    Node* adjList = graph->adjList[vertex];
    Node* temp = adjList;


    graph->visited[vertex] = 1;
    printf("Visited %d \n", vertex);


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


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

int main() {
    Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);


    DFS(graph, 0);


    return 0;
}

You can also try this code with Online C Compiler

Run Code

In this code:

1. We define a `Node` struct to represent a node in the graph, which contains the vertex & a pointer to the next node.

2. We define a `Graph` struct to represent the graph, which contains the number of vertices, an adjacency list, & a visited array to keep track of visited nodes.

3. The `createNode` function creates a new node with a given vertex.

4. The `createGraph` function creates a graph with a given number of vertices & initializes the adjacency list & visited array.

5. The `addEdge` function adds an edge between two vertices in the graph.

6. The `DFS` function performs the depth-first search traversal starting from a given vertex. It marks the current vertex as visited, prints its value, & recursively calls itself for each unvisited adjacent vertex.

7. In the `main` function, we create a graph, add some edges, & call the `DFS` function starting from vertex 0.

Output :

Visited 0 
Visited 1
Visited 2
Visited 3

This shows the order in which the DFS algorithm visits the vertices of the graph.

Examples

Let's look at a few more examples to better understand how the Depth First Search (DFS) algorithm works.

Example 1

Consider the following graph:

If we start the DFS traversal from vertex 0, the order of visited vertices will be:

Visited 0
Visited 1
Visited 2
Visited 3

The DFS algorithm starts at vertex 0, marks it as visited, & explores its adjacent vertices. It first visits vertex 1, then vertex 3, & finally vertex 2.

Example 2

Consider the following graph:

If we start the DFS traversal from vertex 0, the order of visited vertices will be:

Visited 0
Visited 1
Visited 3
Visited 4
Visited 2

In this example, the DFS algorithm starts at vertex 0, visits vertex 1, then vertex 3. From vertex 3, it visits vertex 4 before backtracking & visiting vertex 2.

Time & Space Complexity

Time Complexity

The time complexity of DFS is O(V + E), where V is the number of vertices & E is the number of edges in the graph.

In the worst case, DFS may visit all the vertices & edges of the graph. This happens when the graph is connected & the DFS traversal starts from a vertex that is connected to all other vertices.

Let’s discuss the time complexity in more detail:

Visiting each vertex takes O(V) time because we need to mark each vertex as visited & process it.
Exploring each edge takes O(E) time because, for each vertex, we need to explore all its adjacent vertices, which is equal to the number of edges connected to that vertex.

Therefore, the total time complexity is O(V + E).

Space Complexity

The space complexity of DFS depends on the implementation & the graph's structure.

If we use an adjacency list representation of the graph & implement DFS using recursion, the space complexity will be O(V) in the worst case.

Let’s discuss the space complexity in more depth:

- The adjacency list representation of the graph takes O(V + E) space, where V is the number of vertices & E is the number of edges.

- The recursion stack in DFS can go up to the depth of the graph, which can be at most V in the worst case (for a skewed tree-like graph). Each recursive call requires a constant amount of space on the stack.

- The visited array or hash table used to keep track of visited vertices takes O(V) space.

Therefore, the total space complexity is O(V + E) + O(V) = O(V + E).

However, if the graph is represented using an adjacency matrix & DFS is implemented using recursion, the space complexity will be O(V^2) due to the adjacency matrix representation.

Point to be Noted: It's important to remember that the space complexity can be reduced to O(V) by using an iterative approach with a stack data structure instead of recursion. In this case, the stack will store the vertices to be visited, & its size will be at most V.

Frequently Asked Questions

Can DFS be used to find the shortest path between two vertices in a graph?

No, DFS is not guaranteed to find the shortest path between two vertices. It explores the graph in a depth-first manner, which may not always lead to the shortest path.

Is DFS applicable to both directed & undirected graphs?

Yes, DFS can be used to traverse both directed & undirected graphs. The only difference is in the way the edges are represented in the adjacency list or matrix.

What is the main advantage of using DFS over BFS (Breadth-First Search)?

DFS has the advantage of using less memory than BFS because it doesn't need to store all the nodes at a given level. DFS is also preferred when the goal is to explore deep into the graph or tree structure.

Conclusion

In this article, we have learned about the Depth-First Search (DFS) algorithm, which is a fundamental graph traversal technique. We discussed how DFS works, its pseudocode, & its implementation in C. We also looked at examples to understand how DFS traverses a graph by exploring as far as possible along each branch before backtracking. Moreover, we explained the time & space complexity of DFS & its applications in solving various graph-related problems.