topological sort cp algorithms
int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;
void dfs(int v) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u])
dfs(u);
}
ans.push_back(v);
}
void topological_sort() {
visited.assign(n, false);
ans.clear();
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs(i);
}
reverse(ans.begin(), ans.end());
}Topological sort
L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)
function visit(node n)
if n has a permanent mark then
return
if n has a temporary mark then
stop (not a DAG)
mark n with a temporary mark
for each node m with an edge from n to m do
visit(m)
remove temporary mark from n
mark n with a permanent mark
add n to head of Ltopological 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;
}
}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)Copyright © 2021 Codeinu
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems resetting your password contact us
