Topological Sort: Algorithm, Examples, Time Complexity

While learning about graphs in computer science, one of the most important concepts that you will come across is Topological Sort. It is a method of arranging the nodes in a directed graph so that each node comes before the nodes to which it is connected. It is very helpful for showing the order in which tasks should be executed. If you want to understand what it is and how it is used in real-world situations, you are in the right place. In this blog, you will learn everything about Topological Sort in Data Structure, analyze its time complexity, the algorithms that are used to find topological sorting, its implementation, and its applications.

Table of Contents

• What is Topological Sort in Data Structures?
• Key Characteristics of Topological Sort
• Algorithms for Topological Sort
  1. Kahn’s Algorithm (BFS)
  2. Depth First Search (DFS)
• Implementation of Topological Sort
  1. C++ Implementation
  2. Java Implementation
  3. Python Implementation
• Time Complexity Analysis of Topological Sort
• Advantages and Disadvantages of Topological Sort
• Applications of Topological Sort
• Topological Sort vs DFS vs BFS
• Best Practices
• Common Mistakes to Avoid
• Conclusion

What is Topological Sort in Data Structures?

Topological Sort in Data Structure is basically a way to arrange the vertices of a Directed Acyclic Graph (DAG) in a linear order such that for every edge u -> v, vertex u comes before vertex v in the order.

For example, say we have a graph:

a -> b -> c

Here, this algorithm will return [a,b,c]. This is because a points to b, which means that a must come before b in the sort. Again, b points towards c, which means that b must come before c in the sort.

Example of Topological Sort

Suppose you have a graph consisting of 6 vertices (0 to 5) and the following directed edges:

[2, 3], [3, 1], [4, 0], [4, 1], [5, 0], [5, 2]

This means that:

• Vertex 2 points to 3
• Vertex 3 points to 1
• Vertex 4 points to 0 and 1
• Vertex 5 points to 0 and 2

Output:

The output for this graph is:

5 4 2 3 1 0

Explanation: Here, the first vertex in the ordering is always a vertex with in-degree 0. This means that no edges are coming into it. For the given graph, one possible output can be:

5 4 3 2 1 0

Also, remember that a graph can have more than one valid topological order. For example, another topologically sorted values for the same graph is:

4 5 2 3 1 0

Both these orders follow the same rule, which is that each vertex appears before all the vertices it points to. This is the main idea behind Topological Sort.

Unlock Python: Supercharge Your Coding Skills

Practice coding with hands-on projects and examples to quickly level up your Python skills.

Explore Program

Key Characteristics of Topological Sort

While learning about Topological Sort in Data Structure, it is important for you to understand its main characteristics. Some key characteristics are listed below:

1. Works Only on DAGs: This algorithm can only be applied to a Directed Acyclic Graph (DAG). If the graph has a cycle, then topological sort is not possible.

2. Linear Ordering of Vertices: It helps to produce a linear sequence of vertices such that for every directed edge u -> v, vertex u comes before vertex v.

3. Multiple Valid Orders: A single graph may contain more than one valid Topological Sort. All of them fulfill the rule of dependencies.

4. First Vertex Has No Incoming Edges: The very first vertex always has an in-degree of 0. This means no other vertex points to it.

5. Preserves Dependency Order: This algorithm helps to ensure that all the dependencies are preserved. That is why it is useful for scheduling tasks, course planning, or compiling code.

6. Can be implemented using DFS or BFS: It can be performed using DFS (Depth First Search) and BFS (Breadth First Search). Both these methods give valid results.

Algorithms for Topological Sort

In order to find the topologically sorted order of any graph, there are 2 algorithms that can be used. They are: Kahn’s Algorithm or Breadth-First Search (BFS) and Depth-First Search (DFS).  Both these algorithms are explained below in detail.

1. Kahn’s Algorithm (BFS)

Topological Sort using Kahn’s Algorithm (BFS) uses the in-degrees of vertices. You have to start with the vertices that have no incoming edges (in-degree 0). When the in-degree of a vertex becomes 0, you have to add it to the queue.

The algorithm is given below in a step-by-step manner:

1. At first, you have to look for a vertex with an in-degree of 0. This means that there are no other vertices pointing to it.

2. In the next step, you need to delete all the edges that go from this vertex to other vertices. This helps to make the in-degree of the starting vertex 0.

3. You then have to place that vertex in the array (or list) that keeps track of the sorting process.

4. You have to keep repeating this process of finding vertices with in-degree 0. You can do this by removing their outgoing edges and then including them in the order until all the vertices are added.

Now let’s apply these steps to a sample graph:

Step 1: At first, you have to find out the vertices that have an in-degree of 0. By looking at the graph, A is the only vertex with no incoming edges. Therefore, the vertex that we can pick for Topological Sort is: A

Our graph looks like this now:

Step 2: Here, after you have picked a vertex, you have to remove all the edges that are going outward from it. Therefore, edges from A -> B and A -> C are removed. Now the graph looks like this:

Step 3: Now, after removing the edges from A, you have to check for the vertices that have no incoming edges. B and C are the two vertices that do not have any incoming edges. Now, between B and C, let’s pick B. Now remove the outgoing edges B -> D and B -> E. Now the graph looks like this:

Step 4: The next eligible node is D. However, you can also choose to pick E since it does not contain any remaining connections. It is completely isolated now. Also, remember that there can be more than one valid order as the output. Therefore, choosing D or E at first will not change the correctness of the final order. Both orders will give you the sorting of the graph. Now, the array is [A, B, D] (C and E can be picked next as both have no incoming edges). Now, your graph looks like this:

Step 5: Now, C and E are the remaining nodes with no incoming edges. Pick C first and remove its outgoing edge (C -> F). After this, F will have no incoming edges and can be added next. Then, add E, which is already separate from the others. Finally, add F. Now the array looks like: [A, B, D, C, E, F].

This is your final topologically sorted array for the graph using Kahn’s algorithm.

The Pseudocode for Kahn’s algorithm is given below:

TopologicalSortKahn(Graph G):
    inDegree = array of 0 for all vertices
    for each vertex v in G:
        for each neighbor u of v:
            inDegree[u] += 1

    queue = all vertices with inDegree 0
    topOrder = empty list

    while queue is not empty:
        vertex = queue.pop()
        topOrder.append(vertex)
        for each neighbor u of vertex:
            inDegree[u] -= 1
            if inDegree[u] == 0:
                queue.push(u)

    print topOrder

2. Depth First Search (DFS)

For sorting using DFS, you need to explore the vertices of each neighbor recursively. Once you have visited all the neighbors of a vertex, you have to add the vertex to a stack. After you have visited all the vertices, popping the stack gives you the proper order.

The algorithm is given below in a step-by-step manner:

1. At first, you need to mark all the vertices that are not visited.

2. For each unvisited vertex, you have to do DFS recursively.

3. After you have visited all the neighbors of a particular vertex, you have to push it to a stack.

4. Once you have completed DFS for all the vertices, you need to pop the stack to get the correct order.

Now, let us show how sorting occurs using DFS.

Step 1: At first, you need to build a graph having n vertices and m edges. This graph will represent the connections between nodes.

Step 2:  You need to make two things ready: a stack (for storing the order of nodes) and a visited array (to help keep track of the nodes that you have explored).

Step 3: In the third step, you need to go through each vertex in the graph. If you find a node that has not been visited yet, you have to start a DFS from that particular node.

Step 4: Once you have started the DFS function, you have to mark the current node as visited. After that, you should visit all the unvisited neighbors of that node and call DFS on them one by one.

Step 5: After you have visited all the neighbors of a node, you need to push that node into the stack. This means you have already explored that branch.

Step 6: Once you have visited all the nodes, you have to start popping the elements from the stack one by one and then add them to your final list.

Step 7: The final list that you will get after popping elements from the stack is your topologically sorted order of the graph.

The pseudocode for Topological Sort using DFS is given below:

TopologicalSortDFS(Graph G):
    stack = empty
    visited = array of false for all vertices

    for each vertex v in G:
        if not visited[v]:
            DFS(v)

    while stack is not empty:
        print stack.pop()

DFS(vertex v):
    visited[v] = true
    for each neighbor u of v:
        if not visited[u]:
            DFS(u)
    stack.push(v)

Implementation of Topological Sort

Now, we are going to discuss the implementation in C++, Java, and Python.

1. C++ Implementation

Given below is a C++ code that shows the implementation.

Code:

Output:

Explanation:

The above C++ code is used to take a directed graph. After that, it gives the topological ordering of the vertices using DFS as the output.

2. Java Implementation

Given below is a Java code that shows the implementation.

Code:

Output:

Explanation:

The above Java program is used to perform a DFS on a directed graph. This produces a topological ordering of the vertices.

3. Python Implementation

Given below is a Python code that shows the implementation.

Code:

Output:

Explanation:

The above Python code uses DFS to find and print one possible topological order of a graph.

Time Complexity Analysis of Topological Sort

To understand the efficiency of Kahn’s algorithm in topological sort, let’s break it down step-by-step:

1. Calculating the indegree of each node – O(M): Here, let us take the number of edges to be M. In order to find the indegree (number of incoming edges) for each node, you must check every directed edge in the graph once. Hence, this step will take O(M) time.

2. Finding nodes with zero degree – O(N): In this step, you need to check each node if it has any incoming edges. Since you need to go through all the nodes once, the time taken will be O(N) time, where N is the total number of nodes in the graph.

3. Processing nodes and updating degrees – O(N + M): Here, each node is processed exactly once (O(N)), and for every edge, you have to decrease the in-degree of its neighbor (O(M)). Therefore, combining these two operations will make the step O(N + M).

4. Checking for cycles of completion – O(1): At the end, you simply need to check whether all the nodes are included in the sorted list or if a cycle exists. These steps take a constant time, which is O(1).

Advantages and Disadvantages of Topological Sort

Now, in this section, we are going to talk about the advantages and disadvantages of Topological Sort in data structures.

Advantages

1. The Topological Sort algorithm allows you to find a sequence in which tasks can be performed without violating the dependencies. This can be very useful in scheduling tasks.

2. While you are performing a topological sort in a data structure, if it is not possible to do a valid ordering, then it indicates that the graph has a cycle. This helps in detecting errors.

3. This algorithm has a time complexity of O(N + M). This makes it efficient for graphs that have many nodes and edges.

4. It is also very useful in scenarios like build systems, course prerequisites, or for scheduling tasks, where you have to handle dependencies properly.

Disadvantages

1. You cannot apply the Topological Sort algorithm in a data structure to graphs having cycles. This is because it is not possible to arrange the nodes in a straight line.

2. There can be more than one valid topological ordering. Therefore, it does not provide a unique solution.

3. If the graph changes frequently, you have to perform this sorting, which can be an inefficient task.

4. While Topological Sort provides the order of nodes, it cannot determine the shortest path or the minimum cost between nodes in a graph.

Applications of Topological Sort

1. By using the Topological Sort algorithm, you can easily find if a graph has a cycle. This is because if a valid ordering is not possible, it means that the graph contains a cycle. This is one of the common topological sort examples in analyzing graphs.

2. It also helps to detect deadlocks in operating systems. This is done by checking if the tasks or processes can be ordered without violating the dependencies of the resource. This serves as another example of Topological Sort.

3. It can also be used in project management to schedule tasks or plan projects by respecting the task dependencies. This is one of the most common sorting examples in real-world applications.

Topological Sort vs DFS vs BFS

Now, we are going to talk about the differences between Topological Sort, DFS, and BFS in a tabular format for your reference:

Best Practices 

1. It works properly only on DAGs (Directed Acyclic Graphs). Therefore, you need to ensure that your graph does not have any cycles.

2. You should always use DFS-based Topological Sort for recursive solutions, and for an in-degree-based solution, you need to use BFS-based sorting.

3. You should always keep a track of the visited nodes in DFS or in-degrees in Kahn’s algorithm for avoiding visiting nodes again and again.

4. You also need to check for cycles first so that you can avoid incorrect topological order in graphs that are not DAGs.

5. You should also push nodes after visiting all neighbors in DFS. You can also choose to use a queue for nodes with zero in-degree in Kahn’s algorithm for ordering them correctly.

Common Mistakes to Avoid

1. The Topological Sort algorithm only works on DAGs. Using it on cyclic graphs will give you incorrect results.

2. In DFS-based sorting, if you forget an array that you have visited earlier, you need to revisit the nodes, and this also gives you the wrong ordering.

3. Failing to decrease the in-degrees of neighbors properly can prevent the nodes from entering the zero in-degree queue.

4. Many DAGs consist of multiple valid topological orders. It can be misleading for you if you think there is only one valid topological order.

5. If the graph has nodes that are disconnected, then skipping them can result in an incomplete topological order.

Start Coding in Python for Free: No Experience Needed

Begin writing real Python code through interactive, beginner-friendly modules completely for free.

Explore Program

Conclusion

The Topological Sort algorithm is a powerful tool in graph theory that helps you determine a valid order of tasks or nodes in a DAG (Directed Acyclic Graph). It is used widely in real-world applications like task scheduling, planning projects, and dependency resolution. Having a good understanding of its working, advantages, disadvantages, best practices, and common mistakes, you can apply it in a data structure effectively so that you can avoid errors efficiently and solve complex problems. Mastering Topological Sort ensures that you can handle any situation where node ordering based on dependencies is required.

Boost your career by joining the Python Course today and build real hands-on skills. Get ready for job interviews with expert-curated Python Interview Questions.

Topological Sort – FAQs