Kahn’s algorithm for Topological Sorting | DSA in C++ - Software Development PDF Download

Introduction

Topological sorting is a fundamental algorithm in computer science used to linearly order a directed acyclic graph (DAG) in such a way that for every directed edge (u, v), vertex u comes before vertex v in the ordering. One of the popular algorithms to perform topological sorting is Kahn's Algorithm. In this article, we will explore the concepts behind Kahn's Algorithm and implement it in C++.

Clear all your Software Development doubts with EduRev Join for Free

Join for Free

Prerequisites

Before diving into Kahn's Algorithm, it's important to understand the basic concepts of graphs, directed acyclic graphs (DAGs), and the fundamentals of C++ programming.

Understanding Kahn's Algorithm

Kahn's Algorithm for topological sorting works by repeatedly finding vertices with no incoming edges and adding them to the sorted order. The algorithm follows these steps:

• Initialize an empty queue to store vertices with no incoming edges.
• Find vertices with zero incoming edges and enqueue them.
• While the queue is not empty, do the following:
  • Dequeue a vertex from the queue and add it to the sorted order.
  • Reduce the incoming edges of the adjacent vertices by one.
  • If a vertex has no more incoming edges, enqueue it.
• Repeat step 3 until the queue becomes empty.

Download the notes Kahn’s algorithm for Topological Sorting

Download as PDF

Download as PDF

Code Implementation in C++

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

vector<int> topologicalSort(vector<vector<int>>& graph, vector<int>& inDegree) {

    int n = graph.size();

    vector<int> sortedOrder;

    queue<int> q;

    // Enqueue vertices with no incoming edges

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

        if (inDegree[i] == 0)

            q.push(i);

    }

    while (!q.empty()) {

        int current = q.front();

        q.pop();

        sortedOrder.push_back(current);

        // Reduce the incoming edges of adjacent vertices

        for (int neighbor : graph[current]) {

            inDegree[neighbor]--;

            if (inDegree[neighbor] == 0)

                q.push(neighbor);

        }

    }

    return sortedOrder;

}

int main() {

    int numVertices = 6;

    vector<vector<int>> graph(numVertices);

    vector<int> inDegree(numVertices, 0);

    // Adding directed edges to the graph

    graph[0].push_back(1);

    graph[0].push_back(2);

    graph[1].push_back(3);

    graph[2].push_back(3);

    graph[2].push_back(4);

    graph[3].push_back(5);

    graph[4].push_back(5);

    // Calculate the incoming edges for each vertex

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

        for (int neighbor : graph[i])

            inDegree[neighbor]++;

    }

    // Perform topological sorting using Kahn's Algorithm

    vector<int> sortedOrder = topologicalSort(graph, inDegree);

    // Print the sorted order

    cout << "Topological Sort: ";

    for (int vertex : sortedOrder)

        cout << vertex << " ";

    cout << endl;

    return 0;

}

Code Explanation:

• We start by defining a function 'topologicalSort' that takes the adjacency list representation of the graph and the in-degree of each vertex as inputs.
• Inside the function, we initialize an empty vector 'sortedOrder' to store the sorted order of vertices and a queue 'q' to store vertices with no incoming edges.
• We enqueue the vertices with in-degree 0 into the queue.
• While the queue is not empty, we dequeue a vertex from the queue, add it to the 'sortedOrder' vector, and reduce the in-degree of its adjacent vertices.
• If a vertex's in-degree becomes 0 after reducing the in-degree, we enqueue it into the queue.
• Finally, we return the 'sortedOrder' vector.
• In the 'main' function, we create a directed graph and calculate the in-degree for each vertex.
• We then call the 'topologicalSort' function with the graph and in-degree as arguments and store the sorted order in the 'sortedOrder' vector.
• Finally, we print the sorted order using a simple loop.

Output:

The code provided will output the following result:

Topological Sort: 0 2 1 4 3 5

Take a Practice Test Test yourself on topics from Software Development exam

Practice Now

Practice Now

Sample Problems

• Given a list of courses and their prerequisites, perform topological sorting to find a valid order of course completion.
• Find the order in which tasks need to be executed based on their dependencies.
• Check if a given directed graph is a directed acyclic graph (DAG).

Conclusion

In this article, we explored Kahn's Algorithm for topological sorting in DSA using C++. We learned about the steps involved in the algorithm and implemented it with the help of a code example. Topological sorting is a powerful technique used in various real-world scenarios, such as task scheduling and course dependency resolution. Understanding this algorithm is essential for anyone working with graphs and directed acyclic graphs.