我有一个循环有向图。从叶子开始，我希望将附加到下游每个节点的数据传播到从该节点可到达的所有节点。特别是，我需要围绕达到的任何周期持续推送数据，直到周期稳定。
我完全确定这是一个股票图遍历问题。但是，我在尝试找到合适的算法时遇到了相当大的困难——我想我错过了一些关键的搜索关键字。
在我尝试编写自己的半途而废的 O(n^3) 算法之前，任何人都可以指出一个正确的解决方案吗？这个特殊的问题叫什么？
问问题
7512 次
1 回答
30
由于图是循环的（即可以包含循环），我首先将其分解为强连接的组件。有向图的强连通分量是一个子图，其中每个节点都可以从同一子图中的每个其他节点到达。这将产生一组子图。请注意，多个节点的强连通分量实际上是一个循环。
现在，在每个组件中，一个节点中的任何信息最终都会出现在图中的每个其他节点中（因为它们都是可访问的）。因此，对于每个子图，我们可以简单地从其中的所有节点中获取所有数据，并使每个节点都具有相同的数据集。无需继续循环。此外，在此步骤结束时，同一组件中的所有节点都包含完全相同的数据。
下一步是将每个强连接组件折叠成一个节点。由于同一组件内的节点都具有相同的数据，因此基本相同，因此该操作并没有真正改变图形。新创建的“超级节点”将从组件外部的节点继承出或进入组件节点的所有边。
由于我们已经折叠了所有强连接的组件，因此结果图中将没有循环（为什么？因为如果结果节点形成了一个循环，那么它们首先都会被放置在同一个组件中）。结果图现在是有向无环图。没有循环，从所有 indegree=0 的节点（即没有传入边的节点）进行简单的深度优先遍历，将数据从每个节点传播到其相邻节点（即它的“子节点”），应该可以完成工作.
于 2010-08-30T20:24:51.277 回答