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).

Pseudocode[edit]

  • 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) {
            q.push(i);
        }
    }
 
    //remove one node after the other
    while(q.size() > 0) {
        int currentNode = q.front();
        q.pop();
        solution.push_back(currentNode);
        for(int j = 0; j < graph[currentNode].size(); j++) { //remove all edges
            int newNode = graph[currentNode][j];
            indegree[newNode]--;
            if(indegree[newNode] == 0) { //target node has now no more incoming edges
                q.push(newNode);
            }
        }
    }
 
    if(solution.size() < graph.size()) { //not all nodes could have been sorted -> graph contains cycle
        cerr << "Graph contains cycles." << endl;
    }
 
    return solution;
}