topological sort runtime code example
Example 1: topological sort
void dfs_helper(T src, map<int,bool>& visited, list<T> &ordering) {
//Recursive function that will traverse the graph
visited[src] = true;
//go to all nbr of that node that is not visited
for(T nbr:l[src]) {
if(!visited[nbr]) {
dfs_helper(src,visited,ordering);
}
}
ordering.push_front(src);
}
int dfs(T src) {
map<int,bool> visited;
list<T> ordering;
//Mark all nodes as not visited.
//l = adjacency list implemented using std::unordered_map
for(auto p:l) {
T node = p.first;
visited[node] = false;
}
for(auto p:l) {
T node = p.first;
if(!visited[node]) {
dfs_helper(node,visited,ordering);
}
}
//Finally print the list
for(auto node:ordering) {
cout << node << endl;
}
}
Example 2: topological sort
def topological_sort():
for each node:
if visited[node] is False:
dfs(node)
def dfs(node):
visited[node] = True
for nei in neighbours[node]:
dfs(node)
ret.insert_at_the _front(node)