java - 给定邻接列表，如何找出图中节点的支配者列表？

Question

给定 Graph 中所有节点的列表 G、所有现有连接（边）的列表和所有节点的邻接列表列表，如何继续找出给定节点的支配者列表?

我想到的一种方法如下：

对于给定的节点 N，找出从根节点到 N 的所有路径。这些路径的交集会给我一组支配 N 的节点。但是这里的问题是，我如何真正找出路径？特别是在用 JAVA 编码时。

任何有用的答案，特别是，将不胜感激。

谢谢！

Answer 1

我成功地实现了 Tarjan 的算法。

FWIW，它就像：

要找出n占主导地位的一组节点，只需计算从起始节点到其余节点的所有路径（很容易处理，一旦我们有了所有节点的邻接列表）就可以避开n。让这组可到达的节点为R。n占主导地位的节点是R中不存在的节点。也就是说，如果U是给定图的所有节点的集合，则n将支配属于集合UR的节点。