The Open Cybernetics & Systemics Journal

2015, 9 : 359-362
Published 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

Yong Wei
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.

Keywords:

Adjacency matrix, adjacent table, directed acyclic graph, key-value storage, topological sort.