Topological Sort Algorithm

Last Updated on August 17, 2023 by Mayank Dham

In the realm of graph theory and algorithms, the Topological Sort Algorithm stands as a fundamental method with versatile applications. It provides a systematic way to arrange the nodes of a directed acyclic graph (DAG) such that for every directed edge (u, v), node u appears before node v in the ordering. This ordering holds significance in tasks like project scheduling, dependency resolution, and compiling. In this article, we delve into the intricacies of the Topological Sort Algorithm, exploring its mechanics, use cases, and impact on various fields. We will also see the topological sorting example that will help in better understanding.

What is Topological Sort

Topological sort is a technique used in graph theory to order the vertices of a directed acyclic graph (DAG). It ensures that for every directed edge from vertex A to vertex B, vertex A comes before vertex B in the ordering. This is useful in scheduling problems, where tasks depend on the completion of other tasks. The algorithm begins by selecting a vertex with no incoming edges, adding it to the ordering, and removing all outgoing edges from the vertex. This process is repeated until all vertices are visited, and the resulting ordering is a topological sort of the DAG.

Algorithm of a Topological Sort

Here’s a step-by-step algorithm for topological sorting using Depth First Search (DFS):

• Create a graph with n vertices and m-directed edges.
• Initialize a stack and a visited array of size n.
• For each unvisited vertex in the graph, do the following:
• Call the DFS function with the vertex as the parameter.
• In the DFS function, mark the vertex as visited and recursively call the DFS function for all unvisited neighbors of the vertex.
• Once all the neighbors have been visited, push the vertex onto the stack.
• After all, vertices have been visited, pop elements from the stack and append them to the output list until the stack is empty.
• The resulting list is the topologically sorted order of the graph.

Example of a Topological Sort

Code

                        
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Stack;

 class Ideone {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] st = br.readLine().split(" ");
        int n = Integer.parseInt(st[0]);
        int m = Integer.parseInt(st[1]);

        int[][] prerequisites = new int[m][2];
        for (int i = 0; i < m; i++) {
            st = br.readLine().split(" ");
            prerequisites[i][0] = Integer.parseInt(st[0]);
            prerequisites[i][1] = Integer.parseInt(st[1]);
        }
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int u = prerequisites[i][0];
            int v = prerequisites[i][1];

            graph.get(v).add(u);
        }

        int[] ans = findOrder(n, graph);

        for (int val : ans) {
            System.out.print(val + " ");
        }
    }

static int[] findOrder(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        // add your code here
        Stack<Integer> st = new Stack<>();
        boolean[] visi = new boolean[V];
        
        for(int i = 0; i<V; i++){
            if(!visi[i]){
                helper(adj,st,i,visi);
            }
        }
        
        int[] ans = new int[V];
        int i = 0;
        while(st.size() > 0){
            ans[i] = st.pop();
            i++;
        }
        
        return ans;
    }
    
    static void helper(ArrayList<ArrayList<Integer>> adj, Stack<Integer> st,int i,boolean[] visi){
        visi[i] = true;
        for(int nbr:adj.get(i)){
            if(!visi[nbr]){
                helper(adj,st,nbr,visi);
            }
        }
        
        st.push(i);
    }
}

Explanation of Topological Sort
In the topological sort, we create a temporary stack. we first call the helper function for all its adjacent vertices, then push it to a stack. Finally, print the contents of the stack. Note that a vertex is pushed to the stack only when all of its adjacent vertices are already in the stack.

Advantages of the Topological Sort

Some advantages of the topological sort in Java include:

• Efficient ordering.
• Easy implementation using adjacency lists.
• Wide range of applications.
• Low time and space complexity.
• Scalability for large-scale data processing.

Disadvantages of the Topological Sort

Some disadvantages of the topological sort in Java include:

• It only works on directed acyclic graphs (DAGs) and cannot handle cyclic graphs.
• This does not provide a unique solution if there are multiple valid orders for the nodes.
• It may not be the best algorithm for certain graph-related problems, depending on the specific requirements and constraints.
• These may require additional data structures and memory overhead for larger graphs, which can affect performance.

Applications of Topological Sort in Data Structure

Here are some notable applications of topological sort:

1. Task Scheduling:
In project management and task scheduling, topological sort helps determine the optimal order of tasks with dependencies. Each node in the directed acyclic graph (DAG) represents a task, and directed edges represent dependencies between tasks. By performing a topological sort, you can schedule tasks in the correct sequence to ensure that dependent tasks are completed before their dependents.

2. Software Dependency Resolution:
When managing software projects with multiple modules or libraries, topological sort assists in resolving dependencies between software components. The algorithm ensures that dependencies are resolved in the correct order during compilation or deployment, preventing issues arising from missing dependencies.

3. Building Makefiles:
Makefiles in software development specify the sequence of commands required to build an application from its source code. Topological sort can be used to determine the correct order in which source files need to be compiled, taking into account their interdependencies.

4. Compiler Optimizations:
In compilers, topological sort aids in optimizing the order in which code is generated for different program segments. This optimization ensures that variables are allocated in the correct order and that loops are compiled with appropriate loop unrolling techniques.

5. Dependency Analysis:
In software engineering, topological sort is used to analyze dependencies between modules or components. This helps in understanding the relationships between different parts of a software system, enabling better maintenance and modification.

6. Deadlock Detection:
Topological sort can be used in resource allocation systems to detect deadlocks, which occur when processes are waiting for resources that are blocked by other processes. By creating a resource allocation graph and performing a topological sort, you can identify cycles that indicate potential deadlocks.

7. Course Scheduling:
In educational institutions, topological sort can help create efficient course schedules that ensure prerequisites are met. Each course is represented as a node, and prerequisites are represented by directed edges.

8. Event Management:
In event scheduling systems, topological sort assists in determining the optimal order of events or tasks to ensure that no event starts before its prerequisites are completed.

Conclusion
The Topological Sort Algorithm, with its elegant ability to establish a linear order among tasks in a directed acyclic graph, has proven its value in a plethora of scenarios. From orchestrating project schedules to resolving complex dependencies and optimizing compilation processes, this algorithm offers a structured approach that streamlines tasks with interdependencies. As technology continues to advance and the need for efficient task sequencing persists, the Topological Sort Algorithm remains an indispensable tool for engineers, planners, and problem solvers across disciplines.

Frequently Asked Questions(FAQs)

1. What is the topological sort?
In a directed acyclic graph (DAG), topological sort is a linear ordering of the vertices such that, for any directed edge (u, v), u occurs before v in the ordering.

2. What is the purpose of the topological sort?
Topological sort is used to determine a valid ordering of tasks or events that depend on each other, such that each task or event can be executed after all of its dependencies have been satisfied.

3. How is topological sort performed?
Topological sort can be performed using the depth-first search (DFS) algorithm or breadth-first search (BFS) algorithm.

4. Can topological sort be applied to directed graphs that are not acyclic?
No, topological sort can only be applied to directed acyclic graphs (DAGs).

5. What is the time complexity of the topological sort?
The topological sort has an O(V+E) time complexity, where V is the number of graph vertices and E is the number of graph edges.

6. Is the topological sort unique?
No, there can be multiple valid topological sorts for a given DAG.

7. Can a DAG have more than one source vertex?
Yes, a DAG can have more than one source vertex.

8. Can a DAG have more than one sink vertex?
No, a DAG can have at most one sink vertex.

9. How can we detect cycles in a graph using topological sort?
If a cycle exists in a graph, then it cannot have a topological sort. Therefore, if we perform a topological sorting on a graph and find that it is not possible, then we can conclude that the graph contains a cycle.

10. What are some applications of the topological sort?
Topological sort is used in various applications such as task scheduling, dependency resolution, data serialization, and circuit design.