Topological Sort Algorithm according to the Principle of a DAG’s Subgraph is still a DAG after Outputting a Start Node

ABSTRACT

The paper proves that a DAG’s subgraph is still a DAG or empty after deleting a start node. Based on this conclusion, the program loops the DAG and its subgraph as parameters, calls the same method, outputs a start node. Resulting nodes must be a topological sequence when the parameter is empty, so as to implement a topological sort algorithm. This paper also proposes using key-value storage structure to represent a DAG, where each node as the key, the node’s subsequent nodes as the values. Because subsequent nodes must not be start nodes, the remains must be a start nodes set after deleting each node’s subsequent nodes from the nodes set.

Keywords: