图形序列化

Question

我正在寻找一种简单的算法来"序列化"有向图.特别是我有一组在执行顺序上具有相互依赖性的文件,我想在编译时找到正确的顺序.我知道它必须是一件相当普遍的事情 - 编译器会一直这样做 - 但我的google-fu今天一直很弱.什么是'go-to'算法？

Answer 1

拓扑排序(来自维基百科):

在图论中,有向无环图(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)