{"id":762,"date":"2024-10-19T13:54:22","date_gmt":"2024-10-19T08:24:22","guid":{"rendered":"https:\/\/codexplained.in\/?p=762"},"modified":"2025-11-24T15:31:44","modified_gmt":"2025-11-24T10:01:44","slug":"implement-depth-first-search-dfs","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=762","title":{"rendered":"Implement Depth First Search (DFS)"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define the maximum number of vertices in the graph\n#define MAX_VERTICES 10\n\n\/\/ Structure to represent a graph\ntypedef struct Graph {\n    int numVertices;           \/\/ Number of vertices\n    int adjMatrix[MAX_VERTICES][MAX_VERTICES]; \/\/ Adjacency matrix\n} Graph;\n\n\/\/ Function to create a graph with a given number of vertices\nGraph* createGraph(int vertices) {\n    Graph* graph = (Graph*)malloc(sizeof(Graph));\n    graph->numVertices = vertices;\n\n    \/\/ Initialize the adjacency matrix with zeros\n    for (int i = 0; i < vertices; i++) {\n        for (int j = 0; j < vertices; j++) {\n            graph->adjMatrix[i][j] = 0;\n        }\n    }\n    return graph;\n}\n\n\/\/ Function to add an edge to the graph\nvoid addEdge(Graph* graph, int src, int dest) {\n    graph->adjMatrix[src][dest] = 1; \/\/ Add edge from src to dest\n    graph->adjMatrix[dest][src] = 1; \/\/ Since the graph is undirected\n}\n\n\/\/ DFS function\nvoid DFS(Graph* graph, int vertex, int visited[]) {\n    \/\/ Mark the current vertex as visited\n    visited[vertex] = 1;\n    printf("%d ", vertex); \/\/ Print the visited vertex\n\n    \/\/ Recur for all the vertices adjacent to this vertex\n    for (int i = 0; i < graph->numVertices; i++) {\n        if (graph->adjMatrix[vertex][i] == 1 && !visited[i]) {\n            DFS(graph, i, visited);\n        }\n    }\n}\n\n\/\/ Main function to demonstrate DFS\nint main() {\n    Graph* graph = createGraph(5);\n\n    \/\/ Adding edges to the graph\n    addEdge(graph, 0, 1);\n    addEdge(graph, 0, 2);\n    addEdge(graph, 1, 3);\n    addEdge(graph, 1, 4);\n    addEdge(graph, 2, 4);\n\n    \/\/ Array to keep track of visited vertices\n    int visited[MAX_VERTICES] = {0};\n\n    printf("Depth First Search starting from vertex 0:\\n");\n    DFS(graph, 0, visited);\n\n    \/\/ Free the allocated memory\n    free(graph);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation of the Program<\/h3>\n\n\n\n
    \n
  1. Graph Structure<\/strong>: We define a Graph<\/code> structure that contains the number of vertices and an adjacency matrix to represent the edges.<\/li>\n\n\n\n
  2. Creating the Graph<\/strong>: The createGraph<\/code> function initializes the graph with a specified number of vertices. It allocates memory for the graph and sets all entries in the adjacency matrix to zero.<\/li>\n\n\n\n
  3. Adding Edges<\/strong>: The addEdge<\/code> function allows us to add an edge between two vertices in the graph. Since it\u2019s an undirected graph, we update both directions in the adjacency matrix.<\/li>\n\n\n\n
  4. DFS Implementation<\/strong>:\n
      \n
    • The DFS<\/code> function takes the graph, the current vertex, and an array to track visited vertices. It marks the current vertex as visited, prints it, and recursively visits all unvisited adjacent vertices.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Main Function<\/strong>: The main<\/code> function demonstrates the use of the graph by creating one, adding edges, and initiating the DFS from a starting vertex (in this case, vertex 0).<\/li>\n<\/ol>\n\n\n\n
      Output<\/h3>\n\n\n\n
      When the program is executed, it will output the vertices in the order they are visited during the DFS traversal:<\/p>\n\n\n\n
      Depth First Search starting from vertex 0:\n0 1 3 4 2 \n<\/code><\/pre>\n\n\n\n
      Summary<\/h3>\n\n\n\n
      This C program provides a straightforward implementation of Depth First Search using an adjacency matrix representation of a graph. DFS is a powerful algorithm for exploring graphs and has numerous applications in computer science. Understanding its mechanics lays a foundation for tackling more complex graph-related problems.<\/p>\n