Topological Sort Notes

Original link: https://blog.chungzh.cn/articles/topo-sort/

introduce

Given a directed acyclic graph (DAG, Directed Acyclic Graph), sort its vertices such that for each directed edge $(u, v)$ from $u$ to $v$, $u$ Both come before $v$ in the sort. This sort is called topological sorting.

Topological sorting is possible if and only if there are no directed cycles in the graph (i.e. a directed acyclic graph). If the sorting fails, it means that the directed graph has a cycle, not a DAG.

Any directed acyclic graph has at least one topological ordering.

For example: In the course selection system of a school, there is such a rule: each course may have several prerequisite courses. If you want to take a certain course, you must first take the prerequisite courses required by this course. to study. Assuming that a student can only take one course at the same time, then the order in which he completes all the courses he needs, allowed by the course selection system, is a topological order.

In this example, each course corresponds to a vertex in the directed graph, and each prerequisite relation corresponds to a directed edge (from a prerequisite course to a course requiring a prerequisite).

algorithm

Kahn algorithm

In the initial state, the set $S$ contains all points with in-degree $0$, and $L$ is an empty list.

Each time a point $u$ is arbitrarily taken from $S$ and placed in $L$, then all edges of $u$ $(u, v_1), (u, v_2), (u, v_3) \cdots$ are deleted . For edge $(u, v)$, if the in-degree of point $v$ becomes $0$ after the edge is deleted, put $v$ in $S$.

Repeat the above process until the set $S$ is empty. Check if there are any edges in the graph, if there are, then the graph must have a cycle, otherwise return $L$, the order of vertices in $L$ is the result of topological sort.

Basically the framework of BFS.

Code implementation :

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 

 int n , m ; vector < int > G [ MAXN ]; int in [ MAXN ]; // 存储每个结点的入度bool toposort () { vector < int > L ; queue < int > S ; for ( int i = 1 ; i <= n ; i ++ ) if ( in [ i ] == 0 ) S . push ( i ); while ( ! S . empty ()) { int u = S . front (); S . pop (); L . push_back ( u ); for ( auto v : G [ u ]) { if ( -- in [ v ] == 0 ) { S . push ( v ); } } } if ( L . size () == n ) { for ( auto i : L ) cout << i << ' ' ; return true ; } else { return false ; } }

DFS algorithm

Complete topological sorting with DFS: after visiting a node, add it to the header of the current topological sorting.

Code implementation :

When c[u] == 0 , it means that it has never been visited ( dfs(u) is never called); when c[u] == 1 , it means that it has been visited, and all its descendants have been visited recursively (that is, dfs(u) has been called and has returned); when c[u] == -1 , it means that it is being accessed (that is, the recursive call to dfs(u) is in the stack frame and has not yet returned).

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 

 int n , m ; vector < int > G [ MAXN ]; int c [ MAXN ], topo [ MAXN ], t ; bool dfs ( int u ) { c [ u ] = - 1 ; for ( auto v : G [ u ]) { if ( c [ v ] < 0 ) return false ; else if ( c [ v ] == 0 && ! dfs ( v )) return false ; } c [ u ] = 1 ; topo [ -- t ] = u ; return true ; } bool toposort () { t = n ; memset ( c , 0 , sizeof ( c )); for ( int i = 1 ; i <= n ; i ++ ) if ( ! c [ i ]) if ( ! dfs ( i )) return false ; return true ; }

practise

• UVA10305 Ordering Tasks example
• CF1385E Directing Edges

References

• OI Wiki CC BY-SA 4.0
• “Introduction to Algorithm Competitions”

This article is reprinted from: https://blog.chungzh.cn/articles/topo-sort/
This site is for inclusion only, and the copyright belongs to the original author.