Topological sort
From Algorithmist
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; }