# Topological sort

Jump to navigation
Jump to 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 such that if there is an edge from to , then *i* is less than *j*. Note that such an ordering is not necessarily unique.

The algorithm has a complexity of .

## 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;
}
```