Topological sort

From Algorithmist
Jump to: navigation, search

Topological sort is not a sorting algorithm in the sense that we are given a list of comparable items to put in order. It is given the name "sort" because it provides an ordering, albeit of a different type.

Say we have a directed acyclic graph G. Then a topological sort of G is an ordering of its vertices v_{1},v_{2},...,v_{n} such that if there is an edge from v_{i} to v_{j}, then i is less than j. Note that such an ordering is not necessarily unique.

The algorithm has a complexity of O(V+E).


  • indegree(v) counts the number of edges leading into vertex v
for i from 1 to N
    select some vertex v with indegree(v) equal to 0
    add v to our topological sort
    remove v and all edges leading from it

C++ Implementation[edit]

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> topological_sorting(vector< vector<int> > graph) {
    vector<int> indegree (graph.size(), 0);
    queue<int> q;
    vector<int> solution;
    for(int i = 0; i < graph.size(); i++) {
        for(int j = 0; j < graph[i].size(); j++) { //iterate over all edges
            indegree[ graph[i][j] ]++;
    //enqueue all nodes with indegree 0
    for(int i = 0; i < graph.size(); i++) {
        if(indegree[i] == 0) {
    //remove one node after the other
    while(q.size() > 0) {
        int currentNode = q.front();
        for(int j = 0; j < graph[currentNode].size(); j++) { //remove all edges
            int newNode = graph[currentNode][j];
            if(indegree[newNode] == 0) { //target node has now no more incoming edges
    if(solution.size() < graph.size()) { //not all nodes could have been sorted -> graph contains cycle
        cerr << "Graph contains cycles." << endl;
    return solution;