The Open Cybernetics & Systemics Journal
2015, 9 : 359-362Published online 2015 May 29. DOI: 10.2174/1874110X01509010359
Publisher ID: TOCSJ-9-359
Topological Sort Algorithm according to the Principle of a DAG’s Subgraph is still a DAG after Outputting a Start Node
Software School of Shenzhen
Institute of Information Technology, Shenzhen, Guangdong, 518172, P.R.
China.
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.