将循环图简化为树（依赖图-->树）
我正在分析一些代码的依赖关系。假设存在一些相互交织的依赖关系，如下所示：
F
A /|
| / |
| / |
V < V
B<--->C--->E
\ / |
> < |
D<------+
B 依赖于 A 和 C C 取决于 B 和 F E 取决于 C 和 F D 依赖于 B 和 C 以及 E
我们遇到了 B 和 C 的问题，它们相互依赖。他们应该组合成一个超级节点。 我们对 C、E 和 F 有一个问题，它们有一个循环。他们应该组合成一个超级节点。
您最终会得到
A
|
V
super
node
|
|
D
是否有一个好的库或算法源（Java 首选，但愿意接受建议）可以实现这种减少？
循环中的任何节点都组合成单个节点。指向新节点中任何节点的任何节点都应该指向新节点。新节点中的任何节点所指向的任何节点都应导致新节点指向该节点。
谢谢！
I'm analyzing some code for its dependencies. Let's say there are some interwoven dependencies, like so:
F
A /|
| / |
| / |
V < V
B<--->C--->E
\ / |
> < |
D<------+
B depends on A and C
C depends on B and F
E depends on C and F
D depends on B and C and E
We have a problem with B and C, they depend on each other. They should be combined into a super-node.
We have a problem with C and E and F, they have a cycle. They should be combined into a super-node.
You would end up with
A
|
V
super
node
|
|
D
Is there a good library or algorithm source (Java prefered, but open to suggestions) that allows for such reduction?
Any nodes in a cycle are combined into a single node. Any node that pointed to any node in the new node should point to the new node. Any node pointed to by any node in the new node should cause the new node to point to that node.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我相信您要求合并图表的强连接组件。是的？
我不记得算法了，会尝试查找它。
编辑：我们了解到的是 Tarjan 的。我记得不太清楚，无法教授，但是这里是维基百科页面。
我将尝试给出基本想法。给每个节点一个索引#。然后给每个节点一个lowlink #。 lowlink 是从我们开始的根节点的索引：要考虑的第一个可以找到到我们的路径的节点。如果我们的低链接==我们的索引，那么我们就是强连接组件的根。否则，我们与低链路处于同一组件中。通过在整个图中执行此操作，我们可以确定哪些节点是哪些强连接组件的一部分。
I believe you are asking to combine the strongly connected components of the graph. Yes?
I don't remember the algorithm, will try to look it up.
Edit: The one we learned is Tarjan's. I don't remember it well enough to teach, but here is the Wikipedia page.
I'll try to give the basic idea. Give each node an index #. Then give each node a lowlink #. The lowlink is the index of the node at the root from us: the first node to be considered that can find a path to us. If our lowlink == our index, then we are the root of a strongly connected component. Otherwise, we are in the same component as our lowlink is. By doing this over the whole graph, we can determine which nodes are parts of which strongly connected components.