{"id":760,"date":"2024-10-14T14:31:15","date_gmt":"2024-10-14T09:01:15","guid":{"rendered":"https:\/\/codexplained.in\/?p=760"},"modified":"2025-11-24T15:41:37","modified_gmt":"2025-11-24T10:11:37","slug":"topological-sorting-using-dfs-department-of-financial-services","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=760","title":{"rendered":"Topological Sorting using DFS (Department of Financial Services)"},"content":{"rendered":"\n

Key Concepts of Topological Sort<\/h3>\n\n\n\n
    \n
  1. Directed Acyclic Graph (DAG)<\/strong>: Topological sorting can only be applied to DAGs. If the graph has cycles, topological sorting is not possible.<\/li>\n\n\n\n
  2. DFS-Based Approach<\/strong>:\n
      \n
    • Perform DFS traversal on the graph.<\/li>\n\n\n\n
    • Use a stack to keep track of the order of vertices.<\/li>\n\n\n\n
    • After visiting all vertices, the stack will contain the topological sort.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n

      C Program for Topological Sort Using DFS<\/h3>\n\n\n
      \n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 100\n\n\/\/ Structure for the adjacency list node\nstruct Node {\n    int vertex;\n    struct Node* next;\n};\n\n\/\/ Structure for the graph\nstruct Graph {\n    int numVertices;\n    struct Node* adjList[MAX];\n};\n\n\/\/ Function to create a new adjacency list node\nstruct Node* createNode(int vertex) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->vertex = vertex;\n    newNode->next = NULL;\n    return newNode;\n}\n\n\/\/ Function to create a graph with a given number of vertices\nstruct Graph* createGraph(int vertices) {\n    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));\n    graph->numVertices = vertices;\n\n    for (int i = 0; i < vertices; i++) {\n        graph->adjList[i] = NULL; \/\/ Initialize adjacency list\n    }\n    return graph;\n}\n\n\/\/ Function to add an edge to the graph\nvoid addEdge(struct Graph* graph, int src, int dest) {\n    struct Node* newNode = createNode(dest);\n    newNode->next = graph->adjList[src];\n    graph->adjList[src] = newNode;\n}\n\n\/\/ DFS utility function for topological sort\nvoid topologicalSortUtil(struct Graph* graph, int vertex, int visited[], int stack[], int* stackIndex) {\n    visited[vertex] = 1; \/\/ Mark the current vertex as visited\n\n    \/\/ Recur for all the vertices adjacent to this vertex\n    struct Node* temp = graph->adjList[vertex];\n    while (temp) {\n        int adjVertex = temp->vertex;\n        if (!visited[adjVertex]) {\n            topologicalSortUtil(graph, adjVertex, visited, stack, stackIndex);\n        }\n        temp = temp->next; \/\/ Move to the next adjacent vertex\n    }\n\n    \/\/ Push current vertex to stack which stores the result\n    stack[(*stackIndex)++] = vertex;\n}\n\n\/\/ Function to perform topological sort\nvoid topologicalSort(struct Graph* graph) {\n    int visited[MAX] = {0}; \/\/ Array to keep track of visited vertices\n    int stack[MAX];         \/\/ Stack to store the topological order\n    int stackIndex = 0;     \/\/ Index for the stack\n\n    \/\/ Call the utility function for each vertex\n    for (int i = 0; i < graph->numVertices; i++) {\n        if (!visited[i]) {\n            topologicalSortUtil(graph, i, visited, stack, &stackIndex);\n        }\n    }\n\n    \/\/ Print the contents of the stack\n    printf("Topological Sort: ");\n    for (int i = stackIndex - 1; i >= 0; i--) {\n        printf("%d ", stack[i]);\n    }\n    printf("\\n");\n}\n\n\/\/ Main function\nint main() {\n    struct Graph* graph = createGraph(6); \/\/ Create a graph with 6 vertices\n\n    \/\/ Adding edges to the graph\n    addEdge(graph, 5, 2);\n    addEdge(graph, 5, 0);\n    addEdge(graph, 4, 0);\n    addEdge(graph, 4, 1);\n    addEdge(graph, 2, 3);\n    addEdge(graph, 3, 1);\n\n    \/\/ Perform topological sort\n    topologicalSort(graph);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code<\/h3>\n\n\n\n
        \n
      1. Graph Representation<\/strong>:\n
          \n
        • The graph is represented using an adjacency list, where each vertex points to a list of its neighbors. The Node<\/code> structure is used to represent each vertex’s adjacent nodes.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Graph Functions<\/strong>:\n
            \n
          • createNode<\/strong>: Creates a new node for the adjacency list.<\/li>\n\n\n\n
          • createGraph<\/strong>: Initializes a graph with a specified number of vertices.<\/li>\n\n\n\n
          • addEdge<\/strong>: Adds a directed edge from src<\/code> to dest<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Topological Sort using DFS<\/strong>:\n
              \n
            • The topologicalSortUtil<\/code> function performs a DFS traversal.<\/li>\n\n\n\n
            • It marks each vertex as visited and recurses through its adjacent vertices.<\/li>\n\n\n\n
            • Once all adjacent vertices are processed, the current vertex is pushed onto a stack.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Main Function<\/strong>:\n
                \n
              • In the main<\/code> function, we create a graph with 6 vertices and add directed edges. Then, we call the topologicalSort<\/code> function to perform the sorting and print the result.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Input and Output<\/h3>\n\n\n\n
                Input (Edges of the graph):<\/h4>\n\n\n\n
                The directed edges added to the graph are:
                5 \u2192 2
                5 \u2192 0
                4 \u2192 0
                4 \u2192 1
                2 \u2192 3
                3 \u2192 1<\/pre>\n\n\n\n
                  \n
                • <\/li>\n<\/ul>\n\n\n\n
                  Output<\/h4>\n\n\n\n
                  When you run the program, you will see the following output:<\/p>\n\n\n\n
                  Topological Sort: 4 5 0 2 3 1 
                  <\/code><\/pre>\n\n\n\n
                  Conclusion<\/h3>\n\n\n\n
                  This program demonstrates how to perform topological sorting using DFS on a directed graph. It effectively handles the ordering of vertices to satisfy the prerequisite conditions. You can modify the graph structure by changing the edges to observe different topological sorts. This implementation serves as a good introduction to graph algorithms and their applications in real-world problems, such as scheduling tasks and resolving dependencies.<\/p>\n