{"id":781,"date":"2024-10-14T14:29:42","date_gmt":"2024-10-14T08:59:42","guid":{"rendered":"https:\/\/codexplained.in\/?p=781"},"modified":"2025-11-24T15:41:54","modified_gmt":"2025-11-24T10:11:54","slug":"topological-sorting-using-kahns-algorithm","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=781","title":{"rendered":"Topological Sorting using Kahn\u2019s Algorithm"},"content":{"rendered":"\n

Key Concepts of Kahn’s Algorithm<\/h3>\n\n\n\n
    \n
  1. Directed Acyclic Graph (DAG)<\/strong>: Kahn\u2019s Algorithm can only be applied to DAGs. If the graph has cycles, it cannot be sorted topologically.<\/li>\n\n\n\n
  2. In-degree<\/strong>: Each vertex has an in-degree that counts how many edges are directed toward it.<\/li>\n\n\n\n
  3. Steps of Kahn\u2019s Algorithm<\/strong>:\n
      \n
    • Calculate the in-degree of each vertex.<\/li>\n\n\n\n
    • Initialize a queue with all vertices that have an in-degree of zero.<\/li>\n\n\n\n
    • Repeatedly remove a vertex from the queue, add it to the topological order, and decrease the in-degree of its neighbors. If a neighbor\u2019s in-degree becomes zero, add it to the queue.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n

      C Program for Topological Sort Using Kahn\u2019s Algorithm<\/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\/\/ Function to perform topological sort using Kahn\u2019s Algorithm\nvoid topologicalSort(struct Graph* graph) {\n    int inDegree[MAX] = {0}; \/\/ Array to store in-degrees of all vertices\n    int topologicalOrder[MAX]; \/\/ Array to store the topological order\n    int index = 0;\n\n    \/\/ Calculate in-degrees of all vertices\n    for (int i = 0; i < graph->numVertices; i++) {\n        struct Node* temp = graph->adjList[i];\n        while (temp) {\n            inDegree[temp->vertex]++;\n            temp = temp->next;\n        }\n    }\n\n    \/\/ Initialize queue for vertices with in-degree of 0\n    int queue[MAX], front = 0, rear = 0;\n    for (int i = 0; i < graph->numVertices; i++) {\n        if (inDegree[i] == 0) {\n            queue[rear++] = i; \/\/ Enqueue vertex with in-degree 0\n        }\n    }\n\n    \/\/ Process the queue\n    while (front < rear) {\n        int currentVertex = queue[front++]; \/\/ Dequeue vertex\n        topologicalOrder[index++] = currentVertex; \/\/ Store in topological order\n\n        \/\/ Decrease in-degree for all neighbors\n        struct Node* temp = graph->adjList[currentVertex];\n        while (temp) {\n            inDegree[temp->vertex]--;\n            \/\/ If in-degree becomes 0, enqueue the neighbor\n            if (inDegree[temp->vertex] == 0) {\n                queue[rear++] = temp->vertex;\n            }\n            temp = temp->next; \/\/ Move to next neighbor\n        }\n    }\n\n    \/\/ Check if there was a cycle\n    if (index != graph->numVertices) {\n        printf("The graph has a cycle. Topological sort is not possible.\\n");\n        return;\n    }\n\n    \/\/ Print the topological order\n    printf("Topological Sort: ");\n    for (int i = 0; i < index; i++) {\n        printf("%d ", topologicalOrder[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. Each vertex points to a list of its adjacent vertices using the Node<\/code> structure.<\/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
          • Kahn\u2019s Algorithm<\/strong>:\n
              \n
            • The topologicalSort<\/code> function calculates the in-degrees of all vertices and initializes a queue with vertices that have an in-degree of zero.<\/li>\n\n\n\n
            • It processes the queue by repeatedly dequeuing a vertex, adding it to the topological order, and reducing the in-degrees of its neighbors. If a neighbor\u2019s in-degree becomes zero, it is added to the queue.<\/li>\n\n\n\n
            • After processing, if the number of vertices in the topological order does not match the total number of vertices, it indicates a cycle.<\/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. We then 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
                When you run the program, you will see the following output:<\/p>\n\n\n\n
                mathematicaCopy codeTopological Sort: 4 5 0 2 3 1 \n<\/code><\/pre>\n\n\n\n
                Conclusion<\/h3>\n\n\n\n
                This program effectively implements Kahn\u2019s Algorithm to perform a topological sort on a directed acyclic graph. It checks for cycles, ensuring that the sort can only be performed on valid DAGs. You can modify the graph structure by changing the edges to observe different topological sorts. This implementation provides a clear understanding of Kahn\u2019s Algorithm and its applications in scheduling and task ordering problems.<\/p>\n