Tìm thứ tự topo trong DAG

1. Tìm 1 thứ tự topo trong DAG sử dụng DFS

Mã giả C++:

vector<int> topo;
void dfs(int u) {
    visited[u] = true;
    for(int v : adj[u])
        if (!visited[v]) dfs(v);
    
    topo.push_back(u);
}

// topological ordering
for(int u = topo.size() - 1; u >= 0; u--)
    cout << u << ' ';

2. Tìm tất cả thứ tự topo trong DAG sử dụng backtracking

Happy coding,

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s