Exploring Time Complexity of Topological Sort Algorithm in Python

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.

def topological_sort(graph, sorted_vertices=None):
    if sorted_vertices is None:
        sorted_vertices = []
    
    # Base case
    if len(sorted_vertices) == len(graph):
        return [vertices[i] for i in sorted_vertices]
    
    # Find indegree of all vertices
    indegrees = [sum(col) for col in zip(*graph)]

    # Find the vertices with indegree zero
    zero_indegrees = [i for i, indegree in enumerate(indegrees) if indegree == 0]
    
    # Append the zero indegree list to sorted
    sorted_vertices.extend([i for i in zero_indegrees if i not in sorted_vertices])
    
    # Create a copy of the graph to avoid modifying the input
    new_graph = [row[:] for row in graph]
    # Remove the zero indegree vertices
    for i in zero_indegrees:
        new_graph[i] = [0] * len(new_graph[i])
    
    # Sort the new graph
    return topological_sort(new_graph, sorted_vertices)

---

Time Complexity (Unoptimized Approach)

The above program implements a topological sort algorithm using a recursive approach.

In the worst-case scenario, the program makes V recursive calls, where V is the number of vertices.

In each recursive call, the program performs the following operations:

1. Finding the Indegree of all Vertices

This operation involves transposing the adjacency matrix and then summing the columns to find the indegree of each vertex.

The transposition itself takes <katex>O(V^{2})</katex> time, and the subsequent summing of columns also takes <katex>O(V^{2})</katex> time, resulting in a total time complexity of <katex>O(V^{2})</katex>.

2. Finding the Vertices with Indegree Zero

This operation involves iterating over the list of indegrees and checking if each indegree is zero. Since there are V indegrees, this operation takes O(V) time.

3. Removing the Zero Indegree Vertices

This operation involves iterating over the list of zero-indegree vertices and setting the corresponding rows in the adjacency matrix to zero.

Since there are at most V zero-indegree vertices, and each row has V elements, this operation takes <katex>O(V^{2})</katex> time.

But the program makes V recursive calls. So, the total time complexity of the recursive call is

O(V * (V^{2} + V + V^{2})) = O(V^{3})

However, this is not the optimal solution since it computes the indegrees of all vertices at each recursive step. This is unnecessary because the indegrees of the vertices that have not been removed do not change.

Also, it uses recursion to sort the graph.

---

Optimized Solution

A more efficient approach would be to use a loop to iteratively remove vertices with zero indegree.

from collections import defaultdict, deque

def topological_sort(vertices, adj_matrix):
    # Create an adjacency list representation of the graph
    graph = defaultdict(list)
    indegrees = {vertex: 0 for vertex in vertices}

    for i, row in enumerate(adj_matrix):
        for j, val in enumerate(row):
            if val == 1:
                graph[vertices[j]].append(vertices[i])
                indegrees[vertices[i]] += 1

    # Initialize a queue with vertices having indegree 0
    queue = deque([vertex for vertex, indegree in indegrees.items() if indegree == 0])

    # Initialize an empty list to store the sorted vertices
    sorted_vertices = []

    # Perform the topological sort
    while queue:
        vertex = queue.popleft()
        sorted_vertices.append(vertex)

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

        # Check for cycles
        if len(sorted_vertices) != len(vertices):
            raise ValueError("Graph contains a cycle")

    return sorted_vertices

---

Time Complexity (Optimized Solution)

The time complexity of the above program can be broken down into four main steps:

1. Creating the Adjacency List Representation

This step involves iterating over the adjacency matrix, which has a time complexity proportional to the number of edges E.

So, it has a time complexity of O(E).

2. Initializing the Queue with Vertices Having Indegree 0

This step involves iterating over the vertices, which takes time proportional to the number of vertices V.

So, it has a time complexity of O(V).

3. Performing the Topological Sort

This step involves iterating over the vertices and their neighbors, resulting in a time complexity proportional to the number of vertices V and edges E.

So, it has a time complexity of O(V + E).

4. Checking for Cycles

This step involves iterating over the vertices, which takes time proportional to the number of vertices V. So, it has a time complexity of O(V).

Overall Time Complexity: O(V + E)

Since each step's time complexity is proportional to V or E, the overall time complexity is proportional to V + E.

So, it has a time complexity of O(V + E) because the algorithm only visits each vertex and edge once.