我有一个循环向图。在开始的叶子，我想连接到每个节点的数据传播到下游，从这个节点访问的所有节点。特别是，我需要继续推动各地正在达到，直到周期稳定的任何周期的数据。

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.

在我试图写我自己的一半称职的​​为O（n ^ 3）算法，可以在一个适当的解决方案，任何人都指向我？什么是的这个所谓的特殊问题？

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?

推荐答案

由于该图是循环（即可以包含周期），我会先分解成强连通分量。有向图的强连通分量是一个子图，其中每个节点是由在同一子所有其他节点可到达的。这将产生一组子图。请注意，一个以上的节点的强连接部件是一个有效的周期。

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.

既然我们已经坍塌的所有强连通分量，将有在得到图（为什么？因为曾经有过的最终节点形成一个循环，他们都被放置在同一组件摆在首位没有周期）。所得到的图现在是一个向无环图。有没有周期，并且从与入度= 0（即没有进入的边缘节点）的所有节点一个简单的深度优先遍历，从每个节点传播数据到其相邻节点（即它的孩子），应把工作做好

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.