Johnnn

Let's go

Unraveling the Depth-First Search Algorithm in Graphs: A Comprehensive Guide

by · Published · Updated

Graphs, with their intricate connections, hold vast amounts of information. Traversing through a graph in a systematic manner is essential for analyzing and extracting valuable insights. One of the fundamental graph traversal algorithms is the Depth-First Search (DFS). In this blog post, we will delve into the inner workings of DFS, understand its algorithmic approach, analyze its time complexity, and provide code examples in C, C++, Python, and Java.

Understanding the Depth-First Search Algorithm:
DFS is an algorithm used to explore or traverse a graph in a depth-first manner. It starts at a given vertex (or node) and explores as far as possible along each branch before backtracking. This algorithm plunges into the depths of a graph, exhaustively exploring each branch before moving on.

DFS Algorithm Steps:

  1. Create a stack to store vertices to be visited.
  2. Initialize a visited array to keep track of visited vertices.
  3. Push the starting vertex onto the stack and mark it as visited.
  4. While the stack is not empty, do the following:
    a. Pop a vertex from the stack.
    b. Process the popped vertex (e.g., print it or perform required operations).
    c. Push all unvisited neighbors of the popped vertex onto the stack.
    d. Mark the popped vertex as visited.
  5. Repeat steps 4a to 4d until the stack is empty.

Time Complexity of DFS:
The time complexity of DFS is O(V + E), where V represents the number of vertices and E represents the number of edges in the graph. This complexity arises from visiting each vertex once and each edge once during the traversal.

Example Graph and Traversal:
Let’s consider the following graph to demonstrate the DFS algorithm:

     A
   /   \
  B     C
 / \   / \
D   E F   G

Starting with vertex A, the traversal would be: A, B, D, E, C, F, G.

Code Examples in C, C++, Python, and Java:

  1. C:
#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTICES 100

// Structure to represent a graph node
struct Node {
    int value;
    struct Node* next;
};

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

// Function to add an edge between two nodes
void addEdge(struct Node* adjacencyList[], int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = adjacencyList[src];
    adjacencyList[src] = newNode;

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

// Function to perform depth-first search
void DFS(struct Node* adjacencyList[], int startVertex, int visited[]) {
    struct Node* currentNode;
    int i;
    int stack[MAX_VERTICES];
    int top = -1;

    visited[startVertex] = 1;
    stack[++top] = startVertex;

    while (top >= 0) {
        int vertex = stack[top--];

        printf("%d ", vertex);

        currentNode = adjacencyList[vertex];

        while (currentNode) {
            int neighbor = currentNode->value;

            if (!visited[neighbor]) {
                stack[++top] = neighbor;
                visited[neighbor] = 1;
            }

            currentNode = currentNode->next;
        }
    }
}

int main() {
    int numVertices = 7;
    struct Node* adjacencyList[MAX_VERTICES] = { NULL };

    addEdge(adjacencyList, 0, 1);
    addEdge(adjacencyList, 0, 2);
    addEdge(adjacencyList, 1, 3);
    addEdge(adjacencyList, 1, 4);
    addEdge(adjacencyList, 2, 5);
    addEdge(adjacencyList, 2, 6);

    int visited[MAX_VERTICES] = { 0 };
    printf("DFS Traversal: ");
    DFS(adjacencyList, 0, visited);

    return 0;
}
  1. C++:
#include<iostream>
#include<stack>
#include<vector>
using namespace std;

// Function to perform depth-first search
void DFS(vector<vector<int>>& adjacencyList, int startVertex, vector<int>& visited) {
    stack<int> st;
    visited[startVertex] = 1;
    st.push(startVertex);

    while (!st.empty()) {
        int vertex = st.top();
        st.pop();

        cout << vertex << " ";

        for (int neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                st.push(neighbor);
            }
        }
    }
}

int main() {
    int numVertices = 7;
    vector<vector<int>> adjacencyList(numVertices);

    adjacencyList[0].push_back(1);
    adjacencyList[0].push_back(2);
    adjacencyList[1].push_back(3);
    adjacencyList[1].push_back(4);
    adjacencyList[2].push_back(5);
    adjacencyList[2].push_back(6);

    vector<int> visited(numVertices, 0);
    cout << "DFS Traversal: ";
    DFS(adjacencyList, 0, visited);

    return 0;
}
  1. Python:
# Function to perform depth-first search
def DFS(adjacencyList, startVertex, visited):
    stack = [startVertex]
    visited[startVertex] = 1

    while stack:
        vertex = stack.pop()
        print(vertex, end=" ")

        for neighbor in adjacencyList[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = 1
                stack.append(neighbor)

# Number of vertices
numVertices = 7

# Creating the adjacency list
adjacencyList = [[] for _ in range(numVertices)]

# Adding edges to the graph
adjacencyList[0].extend([1, 2])
adjacencyList[1].extend([3, 4])
adjacencyList[2].extend([5, 6])

# Initializing visited array
visited = [0] * numVertices

print("DFS Traversal:", end=" ")
DFS(adjacencyList, 0, visited)
  1. Java:
import java.util.*;

class Graph {
    private int numVertices;
    private LinkedList<Integer>[] adjacencyList;

    Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; ++i)
            adjacencyList[i] = new LinkedList();
    }

    void addEdge(int src, int dest) {
        adjacencyList[src].add(dest);
        adjacencyList[dest].add(src);
    }

    void DFS(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        Stack<Integer> stack = new Stack<>();
        visited[startVertex] = true;
        stack.push(startVertex);

        while (!stack.empty()) {
            int vertex= stack.pop();
            System.out.print(vertex + " ");

            Iterator<Integer> iterator = adjacencyList[vertex].listIterator();
            while (iterator.hasNext()) {
                int neighbor = iterator.next();
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        int numVertices = 7;
        Graph graph = new Graph(numVertices);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        System.out.print("DFS Traversal: ");
        graph.DFS(0);
    }
}

Conclusion:
Depth-First Search (DFS) is a powerful algorithm for traversing and exploring graphs. By employing a stack and delving deep into each branch before backtracking, it enables a comprehensive analysis of graph structures. In this blog post, we have covered the DFS algorithm’s steps, analyzed its time complexity, and provided code examples in C, C++, Python, and Java. Understanding DFS is crucial for various graph-based applications, such as cycle detection, topological sorting, and more.

You may also like...