有向无环图遍历...帮助吗? [英] Directed Acyclical Graph Traversal... help?

问题描述

我在这里的深度有点深，需要给朋友打电话.我有一个需要遍历的有向无环图，并且我第一次涉足图论.我最近已经阅读了很多有关它的内容，但不幸的是，我没有时间在学术上弄清楚这一点.有人可以帮我踢一下如何处理这棵树吗?

以下是规则:

• 有 n 个根节点(我称它们为源")
• 有 n 个末端节点
• 源节点带有数字值
• 下游节点(我称它们为工人"节点)对传入值(例如Add，Mult等)执行各种操作.

从下图中可以看到，在d，e或f之前，必须先处理节点a，b和c.

走这棵树的正确顺序是什么?

解决方案

我将研究DAG的线性化，该线性化应该可以通过拓扑排序来实现.

根据我所记得的，线性化基本上是按照不变的顺序进行排序的，即对于所有与其他给定节点NodeA都具有度过度的节点(Node_X)，NodeX出现在NodeA之前. /p>

这意味着，根据您的示例，将首先处理节点a，b和d.节点c秒.节点e和f最后.

http://en.wikipedia.org/wiki/Topological_sorting

a little out of my depth here and need to phone a friend. I've got a directed acyclical graph I need to traverse and I'm stumbling into to graph theory for the first time. I've been reading a lot about it lately but unfortunately I don't have time to figure this out academically. Can someone give me a kick with some help as to how to process this tree?

Here are the rules:

• there are n root nodes (I call them "sources")
• there are n end nodes
• source nodes carry a numeric value
• downstream nodes (I call them "worker" nodes) preform various operations on the incoming values like Add, Mult, etc.

As you can see from the graph below, nodes a, b, and c need to be processed before d, e, or f.

What's the proper order to walk this tree?

解决方案

I would look into linearization of DAGs which should be achievable through Topological sorts.

Linearization, from what I remember, basically sorts in an order which holds to the invariant that for all nodes (Node_X) that have an outdegree to any other given node NodeA, NodeX appears before NodeA.

This would mean that, from your example, nodes a,b, and d would be processed first. Node c second. Nodes e and f, last.

http://en.wikipedia.org/wiki/Topological_sorting

这篇关于有向无环图遍历...帮助吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！