Introduction to topological sorting

In graph theory , Topological sorting is a linear sequence of all vertices of a directed acyclic graph . And the sequence must satisfy the following two conditions ：

Every vertex appears and only once .

If there is one from the top A To the top B The path of , So the vertices in the sequence A Appear at the top B In front of .

If it doesn't exist in the end, the penetration is 0 The node of , That means there are rings , non-existent

Concepts in topology ：

Partial order ： There is no loop between two vertices in a directed graph , As for connectivity , It doesn't matter .

Total order ： On the basis of partial order , Any pair of vertices in a directed acyclic graph also need to have a clear relationship ( Reflected in the figure , It's a one-way connected relationship , Be careful not to connect in two directions , Then it becomes a ring ).

A simple algorithm for topological sorting ： First of all, we need to find any depth of 0 A vertex of , Delete it and all adjacent edges , The finding degree is 0 The summit of , And so on , Until all vertices are deleted . The deletion order of vertices is topological sorting .

void dfs(  ){
  for( Adjacency point K){
        if(K Not visited ){
              Mark K;
             DFS(K);
      }
   }
}