Depth First Search DFS

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components.

Algorithm:

The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit.

1. Initialization:

   • Create a boolean array to mark visited vertices.
   • Initialize all vertices as not visited.

2. DFS Function:

• Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices).
• Mark the chosen vertex as visited.
• Explore the chosen vertex's neighbours:
  • If a neighbour is not visited, recursively call the DFS function on that neighbour.
• Repeat until all reachable vertices are visited.
• 
  
3. Here's a simplified recursive implementation in pseudocode:
4. procedure DFS(vertex): mark vertex as visited for each neighbour of vertex: if neighbour is not visited: DFS(neighbour)

non-recursive (using a stack) implementation:

procedure DFS(startVertex): initialize an empty stack push startVertex onto the stack while the stack is not empty: currentVertex = pop from the stack if currentVertex is not visited: mark currentVertex as visited for each neighbour of currentVertex: if neighbour is not visited: push neighbour onto the stack

Description:

• Stack or Recursion:

  • DFS can be implemented using either a stack or recursion. The stack is often preferred in iterative implementations.

• Visited Array:

  • A Boolean array is maintained to mark whether a vertex has been visited or not. This prevents revisiting vertices and infinite loops in cyclic graphs.

• Connected Components:

  • In a disconnected graph, DFS ensures that every vertex is visited. The algorithm is applied to each unvisited vertex to find connected components.

• Applications:

• DFS is used for various tasks such as topological sorting, cycle detection, pathfinding, and connectivity analysis.

Example:

Let's see how the Depth First Search algorithm works with an example. We use an undirected graph with 5 vertices.

We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack.

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have completed the Depth First Traversal of the graph.

Time Complexity:

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

Space Complexity:

The space complexity of DFS is O(V), where V is the number of vertices. This is due to the space required for the visited array and the stack (or recursion call stack).

Applications of DFS:

The following are some of the applications of DFS

For finding the path
To test if the graph is bipartite
For finding the strongly connected components of a graph
For detecting cycles in a graph

C program - DFS

/*******************************************************************************/

#include <stdio.h>

#define MAX_VERTICES 10

// Function to perform Depth-First Search (DFS)

void dfs(int vertex, int visited[MAX_VERTICES], int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {

    printf("V%d ", vertex ); // Assuming vertex labels are 'V0', 'V1', 'V2', ...

    // Mark the current vertex as visited

    visited[vertex] = 1;

    // Recursively visit all unvisited neighbours

    for (int i = 0; i < numVertices; i++) {

        if (adjacencyMatrix[vertex][i] == 1 && !visited[i]) {

            dfs(i, visited, adjacencyMatrix, numVertices);

    }
 }
}

int main() {

    int numVertices, i, j;

    printf("Enter the number of vertices (max %d): ", MAX_VERTICES);

    scanf("%d", &numVertices);

    // Input the adjacency matrix

    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

    printf("Enter the adjacency matrix (1 for connected, 0 for not connected):\n");

    for (i = 0; i < numVertices; i++) {

        for (j = 0; j < numVertices; j++) {

            scanf("%d", &adjacencyMatrix[i][j]);

    }
}

    // Array to keep track of visited vertices

    int visited[MAX_VERTICES] = {0};

    // Perform DFS starting from each unvisited vertex

    printf("DFS Traversal Order:\n");

    for (i = 0; i < numVertices; i++) {

        if (!visited[i]) {

            dfs(i, visited, adjacencyMatrix, numVertices);

   }
}

  return 0;
}

Output:

Enter the number of vertices (max 10): 5

Enter the adjacency matrix (1 for connected, 0 for not connected):

0 1 1 1 0  

1 0 1 0 0

1 1 0 0 1

1 0 0 0 0

0 0 1 0 0

DFS Traversal Order:

V0 V1 V2 V4 V3 

Example:

Find the DFS of  the following Graph ( university question)

DFS: ABEHFCGD