我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组文件,它们的执行顺序具有相互依赖性,我想在编译时找到正确的顺序。我知道这一定是很常见的事情- 编译器一直都在做-但是我的google-fu今天很薄弱。什么是“去”算法?
拓扑排序(来自维基百科):
在图论中,有向无环图(DAG)的拓扑排序或拓扑排序是其节点的线性排序,其中每个节点先于其具有出站边缘的所有节点出现。每个DAG具有一种或多种拓扑类型。
伪代码:
L ← Empty list where we put the sorted elements Q ← Set of all nodes with no incoming edges while Q is non-empty do remove a node n from Q insert n into L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into Q if graph has edges then output error message (graph has a cycle) else output message (proposed topologically sorted order: L)