Topological Sorting

Authored by HackerRank

Topological Sorting is an ordering of the vertices of a graph such that if a vertex precedes a vertex in the ordering then there does not exist any path from vertex to vertex .
Obviously, this sort of ordering is never possible in a graph which has a directed cycle. And hence, top-sort (a popular abbreviation) can not be done in an undirected graph (since, every edge is actually a directed cycle between its 2 endpoints). So, top-sort is only applicable to Directed Acyclic Graphs (DAGs).

The Algorithm
The most important observation which leads to the algorithm here is:-
Any vertex with in-degree can precede any other vertex in the graph.(*) This is simply because, no vertex can have a path to a vertex with in-degree .
This means, we can safely add any vertex with in-degree as the next vertex in our ordering and delete it from the graph and repeat the same procedure till the graph becomes empty.
One can note that to check if a vertex is removed, one might just check if its in-degree is 0 or not.
Hence, if we represent the graph in the standard adjacency list, the C++ implementation will be like:

vector<int> topSort()  {
  queue<int> Q;
  for(int i=1; i<=n; i++) {
    if(inDegree[i] == 0)  {
      Q.push(i);
    }
  }
  vector<int> res;
  while(not Q.empty())  {
    int now = Q.front();
    res.push_back(now);
    for(int next: graph[now]) {
      if(inDegree[next] > 0)  {
        inDegree[next]--;
        if(inDegree[next] == 0) {
          Q.push(next);
        }
      }
    }
  }
  return res;
}

Complexity and Correctness
Correctness follows directly from the observation (*). In the above implementation, for each vertex, we keep on deleting all the edges coming out from that vertex in time per edge. Hence, the complexity is simply . Since, in-degrees can be calculated while constructing the graph, its also and hence the overall complexity is also .

 
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score