我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组在执行顺序上相互依赖的文件,我想在编译时找到正确的顺序。我知道这一定是一件相当普遍的事情——编译器一直在做——但我的 google-fu 今天一直很弱。这个的“首选”算法是什么?
最佳答案
Topological Sort (来自维基百科):
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.
伪代码:
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)
关于algorithm - 图序列化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4168/