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++.

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.

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

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.