Exploring Time Complexity of Topological sort Algorithm in C++

Topological sorting is an algorithm in graph theory that is used to order the vertices of a directed acyclic graph (DAG) such that for every edge (u, v), vertex u comes before vertex v in the ordering.

In this article, we'll delve into the time complexity of the topological sort algorithm.

---

How Does Topological Sort Work?

Topological sort works by

1. Identifying vertices with no incoming edges (i.e., vertices with an indegree of 0) and adding them to a sorted list.
2. Removing these vertices from the graph and updating the indegrees of the remaining vertices.
3. Repeating this process until all vertices have been added to the sorted list.

vector<int> topological_sort() {

    vector<int> indegrees(num_vertices + 1);
    // Indegree calculation
    for(int i = 1; i <= num_vertices; ++i) {
        for(auto node: adj_list[i]) {
            ++indegrees[node];
        }
    }

    // Queue Initialization
    queue<int> q;
    for(int i = 1; i <= num_vertices; ++i) {
        if(!indegrees[i]) {
            q.push(i);
        }
    }
      
    // Queue Processing
    vector<int> sorted_vertices;
    while(!q.empty()) {
        int current_vertex = q.front();
        sorted_vertices.push_back(current_vertex);
        q.pop();
        for(int destination_vertex: adj_list[current_vertex]) {
            --indegrees[destination_vertex];
            if(!indegrees[destination_vertex]) {
                q.push(destination_vertex);
            }
        }
    }

    return sorted_vertices;
}

---

Time Complexity

The time complexity of this algorithm can be divided into the following components:

1. Indegree Calculation

In this step, we calculate the indegree of each vertex by iterating over all the edges in the graph. Although this involves nested loops, the time complexity is not O(V * E) because the inner loop does not iterate over all vertices for each edge.

Instead, it iterates over all edges incident on each vertex, resulting in a total number of iterations equal to the total number of edges in the graph.

Therefore, the time complexity is O(V + E).

2. Queue Initialization

In this step, we initialize a queue with all the vertices with an indegree of 0. We perform this operation for V vertices.

Thus, the time complexity of this step is O(V).

3. Queue Processing

In this step, we process the queue by removing the vertices with indegree 0 and updating the indegrees of the remaining vertices.

Similar to the Indegree Calculation step, the nested loops do not result in a time complexity of O(V * E) because the inner loop iterates over all edges incident on each vertex, not all vertices for each edge.

As a result, the time complexity is O(V + E).

Overall Time Complexity: O(V + E)

The overall time complexity of the algorithm is the sum of the time complexities of each operation:

O(V + E) + O(V) + O(V + E)

Since O(V + E) dominates O(V), the overall time complexity is O(V + E).