图形序列 [英] graph serialization

问题描述

我在找一个简单的算法来连载有向图。特别是我有一组文件，其执行顺序上的相互依存关系，我想找到正确的顺序在编译时。我知道这一定是一个相当普遍的事情 - 编译器做这一切的时候 - 但我的谷歌福今天一直疲软。什么是去到算法呢？

I'm looking for a simple algorithm to 'serialize' a directed graph. In particular I've got a set of files with interdependencies on their execution order, and I want to find the correct order at compile time. I know it must be a fairly common thing to do - compilers do it all the time - but my google-fu has been weak today. What's the 'go-to' algorithm for this?

推荐答案

的拓扑排序（维基百科）：

在图论，拓扑排序或   的定向拓扑顺序   非循环图（DAG）是线性   它的节点的排序，其中，每个   节点来所有节点之前，该   它有出站的边缘。每个DAG都有   的一个或多个拓扑排序

In graph theory, a topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts.

伪code：

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)

这篇关于图形序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！