CODEWITHSUNDEEP
graphtopological-sort
M. Stephens
M. Stephens

Reputation: 59

What is a Topological Sort

I have looked up numerous examples online and watched a YouTube video but I am still a little lost on what a topological sort is. As far as i understand you should start with like a visited and non-visited queue and get the topological sort order when you are done visiting all of the children of a node?

Upvotes: 2

Views: 3474

Answers (2)

Aditya
Aditya

Reputation: 1058

Topological Sort means you are given a list of jobs and list of prerequisites and you have to figure out the ordering of jobs.

jobs = [1,2,3] prerequisites = [[1,2], [1, 3], [3,2]]

result = [1,3,2] should be the order in which jobs should execute. here [1,2] signifies that job 2 cannot be started until job 1 is completed (job 1 is a prerequisite).

So for this you can use a straightforward depth first search (graph traversal algo). wherein you can have a custom class named with JobVertex

class JobVertex {
   int job;
   List<JobVertex> preRequisites;
   boolean inProgress; 
   boolean visited;}

Initially both inProgress and visited flags can be set to false. inProgress flag is used to detect cycles (because to make topological sort to work graph has to be DAG)

List<Integer> result = new ArrayList<>();

result is the final list where our ordered jobs will be added. dfs(node, result) method can look like this wherein you can start with any of the node and then traverse through its prerequisites in recursive manner and updating the flags with every iteration.

Time Complexity can be same as that of dfs (v + e) where v corresponds to vertices and e corresponds to edges respectively.

Upvotes: 2

A. Picariello
A. Picariello

Reputation: 11

A topological sort is a linear ordering of nodes in which for every directed edge 'a -> b', 'a' comes before 'b' in the ordering. Since the edges must be directed, topological sorts must be done on directed graphs, and the graphs must also be acyclic (they can't contain cycles). This is a special subset of graphs known as a DAG (Directed Acyclic Graph).

Here is an example of what it looks like, notice all edges (arrows) go left to right

The best way to find a topological sort is to use DFS with a temporary Stack as opposed to a Queue. Your understanding is close, but not fully there. As DFS is running on the graph, you don't push the node onto the temporary Stack until all of the children of that node have been explored as well. This is where the recursive element of this algorithm comes into play. Since you don't want to push the node onto the stack until of its children have been explored, you have to wait until the algorithm is finished running on the children. By implementing a stack, the first node that is popped off the top will have no edges pointing towards it, and the last node popped off will have no edges coming from it. If we used a queue it would be the other way around.

You can use a second stack and remove nodes from it once they are added to the temporary stack for housekeeping purposes. Once all the nodes are on the temporary stack, print them by popping them off one by one, and you will have the topological sort of the given graph.

Upvotes: 1

Related Questions