# Topological sort

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

• 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

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