图序列化

发布于 2024-07-05 00:54:14 字数 125 浏览 7 评论 0原文

我正在寻找一种简单的算法来“序列化”有向图。特别是，我有一组执行顺序相互依赖的文件，我想在编译时找到正确的顺序。我知道这一定是一件相当常见的事情 - 编译器一直在这样做 - 但我的谷歌今天一直很弱。这个的“首选”算法是什么？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

多情癖 2024-07-12 00:54:15

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

回复收藏 0 原文

画▽骨i 2024-07-12 00:54:15

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

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）。我能看到的唯一解决方法是将递归算法翻转为具有手动堆栈的交互式算法，并手动检查堆栈中是否有重复元素。

有人有更好的东西吗？

I've come up with a fairly naive recursive algorithm (pseudocode):

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);

The biggest problem with this is that it has no ability to detect cyclic dependencies - it can go into infinite recursion (ie stack overflow ;-p). The only way around that that I can see would be to flip the recursive algorithm into an interative one with a manual stack, and manually check the stack for repeated elements.

Anyone have something better?

回复收藏 0 原文

穿越时光隧道 2024-07-12 00:54:15

我希望需要此功能的工具只需以深度优先的方式遍历树，当它们到达叶子时，只需处理它（例如编译）并将其从图中删除（或将其标记为已处理，并处理具有所有叶子的节点）加工为叶子）。

只要它是 DAG，这种简单的基于堆栈的遍历就应该是微不足道的。

回复收藏 0 原文

若沐 2024-07-12 00:54:14

拓扑排序（来自维基百科）：

在图论中，拓扑排序或
有向的拓扑排序
无环图 (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)

Topological Sort (From Wikipedia):

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.

Pseudo 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)

回复收藏 0 原文

~没有更多了~