有向循环图的遍历
我有一个循环有向图。从叶子开始，我希望将附加到下游每个节点的数据传播到从该节点可到达的所有节点。特别是，我需要不断推送所达到的任何周期的数据，直到周期稳定为止。
我完全确定这是一个股票图遍历问题。然而，我在尝试找到合适的算法时遇到了相当大的困难——我认为我错过了一些关键的搜索关键字。
在我尝试编写自己的半途而废的 O(n^3) 算法之前，有人能给我指出一个正确的解决方案吗？这个特殊问题被称为什么？
I have a cyclic directed graph. Starting at the leaves, I wish to propagate data attached to each node downstream to all nodes that are reachable from that node. In particular, I need to keep pushing data around any cycles that are reached until the cycles stabilise.
I'm completely sure that this is a stock graph traversal problem. However, I'm having a fair bit of difficulty trying to find a suitable algorithm --- I think I'm missing a few crucial search keywords.
Before I attempt to write my own half-assed O(n^3) algorithm, can anyone point me at a proper solution? And what is this particular problem called?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
由于该图是循环的（即可以包含循环），因此我首先将其分解为强连接的组件。有向图的强连通分量是一个子图，其中每个节点都可以从同一个子图。这将产生一组子图。请注意，多个节点的强连接组件实际上是一个循环。
现在，在每个组件中，一个节点中的任何信息最终都会出现在图中的每个其他节点中（因为它们都是可访问的）。因此，对于每个子图，我们可以简单地从其中的所有节点获取所有数据，并使每个节点都具有相同的数据集。无需继续经历循环。此外，在此步骤结束时，同一组件中的所有节点都包含完全相同的数据。
下一步是将每个强连接组件折叠成单个节点。由于同一组件内的节点都具有相同的数据，因此基本相同，因此此操作不会真正改变图形。新创建的“超级节点”将继承从组件外部的节点出入组件节点的所有边。
由于我们已经折叠了所有强连通分量，因此结果图中不会有循环（为什么？因为有如果是由所得节点形成的循环，则它们首先会被放置在同一个组件中）。生成的图现在是一个有向非循环图。没有循环，并且从入度 = 0 的所有节点（即没有传入边的节点）进行简单的深度优先遍历，将数据从每个节点传播到其相邻节点（即其“子节点”），应该可以完成工作。
Since the graph is cyclic (i.e. can contain cycles), I would first break it down into strongly connected components. A strongly connected component of a directed graph is a subgraph where each node is reachable from every other node in the same subgraph. This would yield a set of subgraphs. Notice that a strongly connected component of more than one node is effectively a cycle.
Now, in each component, any information in one node will eventually end up in every other node of the graph (since they are all reachable). Thus for each subgraph we can simply take all the data from all the nodes in it and make every node have the same set of data. No need to keep going through the cycles. Also, at the end of this step, all nodes in the same component contains exactly the same data.
The next step would be to collapse each strongly connected component into a single node. As the nodes within the same component all have the same data, and are therefore basically the same, this operation does not really change the graph. The newly created "super node" will inherit all the edges going out or coming into the component's nodes from nodes outside the component.
Since we have collapsed all strongly connected components, there will be no cycles in the resultant graph (why? because had there been a cycle formed by the resultant nodes, they would all have been placed in the same component in the first place). The resultant graph is now a Directed Acyclic Graph. There are no cycles, and a simple depth first traversal from all nodes with indegree=0 (i.e. nodes that have no incoming edges), propagating data from each node to its adjacent nodes (i.e. its "children"), should get the job done.