Topological Sorting (BFS)

Topological Sorting of a Directed Graph using BFS (Kahn's Algorithm)

Topological sorting is an ordering of vertices in a directed graph such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. This is particularly useful in scenarios like task scheduling, dependency resolution, and build systems. In this blog, we will implement topological sorting using BFS and a queue, commonly known as Kahn's Algorithm.

---

Understanding the Approach

Topological sorting works only for Directed Acyclic Graphs (DAGs). The algorithm involves the following steps:

1. Calculate In-degrees:

   • The in-degree of a vertex is the number of edges directed towards it.

   • Initialize an array to store the in-degrees of all vertices.

2. Initialize Queue:

   • Add all vertices with in-degree 0 to the queue. These vertices do not depend on any other vertices and can be processed first.

3. Process Vertices:

   • Remove a vertex from the queue, add it to the topological order, and decrease the in-degree of its neighbors.

   • If a neighbor's in-degree becomes 0, add it to the queue.

4. Repeat:

   • Repeat until the queue is empty. If all vertices are processed, a topological order is obtained. If not, the graph contains a cycle, and topological sorting is not possible.

---

Pseudo Code

function topologicalSort(graph, V):
    inDegree = [0] * V
    for each vertex in graph:
        for each neighbor of vertex:
            inDegree[neighbor] += 1

    queue = []
    for i from 0 to V-1:
        if inDegree[i] == 0:
            queue.append(i)

    topoOrder = []
    while queue is not empty:
        node = queue.pop()
        topoOrder.append(node)

        for neighbor in graph[node]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                queue.append(neighbor)

    if size of topoOrder == V:
        return topoOrder
    else:
        return "Graph contains a cycle"

---

Implementation in C++

Here is the C++ implementation of topological sorting using a queue:

vector<int> topologicalSort() {
    vector<int> inDegree(V, 0); // Initialize in-degree array

    // Calculate in-degrees of all vertices
    for (int i = 0; i < V; ++i) {
        for (int neighbor : adj[i]) {
            inDegree[neighbor]++;
        }
    }

    queue<int> q; // Queue to store vertices with in-degree 0

    // Add all vertices with in-degree 0 to the queue
    for (int i = 0; i < V; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topoOrder; // To store the topological order

    // Process vertices in the queue
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        topoOrder.push_back(node);

        // Decrease in-degree of neighbors
        for (int neighbor : adj[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // Check if the graph contains a cycle
    if (topoOrder.size() != V) {
        cout << "The graph contains a cycle. Topological sorting is not possible." << endl;
        return {};
    }

    return topoOrder;
}

---

Explanation of Code

1. Graph Initialization:

   • The constructor initializes the graph with a given number of vertices (V).

   • The adjacency list (adj) is resized to accommodate V vertices.

2. Adding Edges:

   • addEdge adds a directed edge from vertex u to vertex v.

3. Calculate In-Degree:

   • Iterate through the adjacency list to compute the in-degree of each vertex.

4. Queue Initialization:

   • Vertices with in-degree 0 are added to the queue.

5. Process Queue:

   • For each vertex removed from the queue, add it to the topological order and reduce the in-degree of its neighbors. Add neighbors with in-degree 0 to the queue.

6. Cycle Detection:

   • If the size of the topological order is less than V, the graph contains a cycle.

---

Time and Space Complexity

• Time Complexity:

  • Calculating in-degrees: O(V + E)

  • Processing vertices: O(V + E)

  • Total: O(V + E)

• Space Complexity:

  • Adjacency list: O(V + E)

  • In-degree array and queue: O(V)

  • Total: O(V + E)

---

Applications

• Task scheduling

• Dependency resolution (e.g., in build systems or package managers)

• Course scheduling in academic curricula