Topological sorting

It is enough just to understand to present the topological sorting as "dependency satisfaction"; the graph in this case is nothing but a set of dependencies of each vertex on any other.

For example, for that link we have a list of dependencies:

1 : 4 2 : 3 : 2 4 : 2, 3 

The essence of the algorithm is reduced to pseudocode:

 [bool, sorted] TopologicalSort(dependencies) { states = new [dependencies.Length]; foreach (var state in states) { state = None; } var result = []; for (var vertex in Range(dependencies.Length)) { if (!Resolve(vertex, dependencies, states)) return [false, []]; } return [true, result]; } [bool] Resolve(vertex, dependencies, states, result) { if (states[vertex] == InProcess) return false; if (states[vertex] == Resolved) return true; states[vertex] = InProcess; foreach (var dep in dependencies[vertex]) { if (!Resolved(dep, dependencies, states, result)) return false; } states[vertex] = Resolved; result.append(vertex); return true; } 

those. we assign a state ("color") to each vertex: None is not processed, InProcess is in the process of resolving dependencies, Resolved is already added to the result.

Then if we are trying to resolve the dependency for the vertex "in process", then it is obvious that there is a cyclic dependency.

An interesting record about topological sorting is in Eric Lippert .

Perhaps this is not exactly the answer to your question, but I think this will help to understand the link .

But generally, a top.sort does the following: puts all the vertices of a directed graph in the order that all the vertices reachable from a particular vertex follow strictly it. And so that this property would be fulfilled for all vertices of the graph. How the non-connected components will be located is absolutely not important for us, since there are no mutually supportive nodes in them.

Topological sorting problem (topsort): a directed graph with N vertices and M edges is given. It is required to renumber its vertices so that each rib leads from a vertex with a smaller number to a vertex with a large one.

To solve, we use depth traversal (dfs (v), v is the vertex from which the traversal is launched).

Suppose the graph is acyclic, i.e. a solution exists. What does the depth crawl do? When launched from some vertex V, it tries to start along all edges emanating from V. It does not pass along those edges whose ends have already been visited, but does not pass along all the others, and runs from its ends.

Thus, by the time of exit from the dfs (V) call, all the vertices reachable from V both directly (one edge) and indirectly (along the path) are all such vertices already visited by the detour. Consequently, if at the moment of exit from dfs (V) we add our vertex to the beginning of a certain list, then in the end this list will have a topological sort.

These explanations can be presented in a slightly different light, with the help of the concept of “time to exit” bypassing in depth. The exit time for each vertex v is the point in time at which the dfs (v) bypass depth call from it has stopped working (exit times can be numbered from 1 to N). It is easy to understand that when going deeper, the exit time from any vertex is always greater than the exit time from all the vertices reachable from it (since they were visited either before the dfs (V) call, or during it). Thus, the desired topological sorting is sorting in descending order of exit times !!!!

Implementation:

 int n; // число вершин vector<int> g[MAXN]; // граф bool used[MAXN]; vector<int> ans; void dfs (int v) { used[v] = true; for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i]; if (!used[to]) dfs (to); } ans.push_back (v); } void topological_sort() { for (int i=0; i<n; ++i) used[i] = false; ans.clear(); for (int i=0; i<n; ++i) if (!used[i]) dfs (i); reverse (ans.begin(), ans.end()); }