Why does this DFS-based topological sort algorithm work?

user_13105710 0
Viewed 434

Here is the algorithm that I pulled from this competitive programming resource. 

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());
}

How does this algorithm avoid adding vertices to the topologically sorted collection that have incoming directed edges? Say, for example, that the first vertex (0 in this example) checked by the for loop has an incoming directed edge from vertex (1). What is stopping this algorithm from outputting (0) before first ensuring that (1) has been output?

topological-sort algorithm
2 Answers

It's building the output vector backwards. If there's an incoming directed edge from vertex (1) to vertex (0), you want to output (0) before (1).

Note that dfs(int v) calls ans.push_back(v) only after it recurses to all its descendants. This ensures that anything that follows v will have been added to the output vector before v. Anything not visited[] after dfs(0) returns is either unrelated to 0 or its descendants (and therefore can be added later), or precedes them (and therefore should be added later).

comingstorm_2102110

As far as I can tell, the DFS approach requires the graph to not have any cycles. If the graph does have cycles, the DFS will not detect it and will give a wrong result. If the graph does not have cycles, the DFS will work. Certain other algorithms than DFS for finding the topological sort can detect cycles and rightly give an error if any cycle exists, since a topological sort is not possible for a graph with cycles. So, it is a very good question you ask.

user_95439440
Related