首页 / 知识

关于算法：图形序列化

2023-04-11 19:02:00

Graph serialization

我正在寻找一种简单的算法来"序列化"有向图。特别是，我有一组文件，它们的执行顺序相互依赖，我想在编译时找到正确的顺序。我知道这一定是很常见的事情-编译器一直都在做-但是我的google-fu今天很薄弱。什么是"去"算法？

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

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.

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

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)

如果图形包含循环，那么如何存在文件的允许执行顺序？
在我看来，如果图形包含周期，那么您将没有解决方案，这
通过上述算法正确报告。

我希望需要这样的工具能够以深度优先的方式在树上行走，当它们碰到叶子时，只需对其进行处理(例如编译)并将其从图形中删除(或将其标记为已处理，并使用所有叶子来处理节点)处理为叶子)。

只要是DAG，这个基于堆栈的简单步行就很容易了。

我想出了一个相当幼稚的递归算法(伪代码)：

1
2
3
4
5
6
7
8
9
10
11

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
if (dest.contains(a)) return;
foreach (b in source[a]):
resolve(b);
dest.add(a);

foreach (a in source):
resolve(a);

最大的问题是它没有能力检测循环依赖关系-它可以进行无限递归(即堆栈溢出；-p)。我能看到的唯一方法是将递归算法转换为带有手动堆栈的交互式算法，并手动检查堆栈中是否存在重复的元素。

有人有更好的东西吗？

算法序列化图形执行顺序