graph-theory - 在有向图中查找孤岛

Question

我正在使用一种晦涩难懂的语言，依赖管理很差。为了帮助 14000 个文件代码库，我编写了一些解析工具(在 Java 中)并生成了一个依赖关系图。

我编写了自己的图形和 BFS 类，它们工作得很好。有了它们，我就有了getParents()这样的方法。和 getChildren() .

现在我试图在这张图中找到“岛屿”；也就是说，我试图找出我们代码库的哪些部分不相互依赖，希望将它们收集到独立的模块中。

稍后，我还计划分析各个岛屿，看看它们是否有任何弱点，我们可以建立模块屏障并定义该模块的接口(interface)，但那是在路上。

现在，我正在考虑这样做:

Map<DependencyEntry, Set<DependencyEntry>> allChildren = new ...;
for(DependencyEntry entry : allFiles) allChildren.put(entry,getAllChildren(entry));
Set<DependencyEntry> visited = new ...;
Set<DependencyEntry> largest = new HashSet<DependencyEntry>(); // size 0
// slightly more expensive but more readable
for(DependencyEntry entry : allChildren.keySet()) {
    Set<DependencyEntry> set = allChildren.get(key);
    if(set.size() > largest.size()) largest = set;
}
visited.addAll(largest);

这应该给我最大的岛屿。从那里，我可以遍历并排除包含任何访问节点的任何集合，然后再次运行它以获得下一个最大的岛，依此类推。

这是一个准确的算法吗？有没有更好的方法来解决我没有看到的这个问题？

Answer 1

听起来你想建立 connected components 的集合在依赖图中找到。从那里您可以迭代集合并确定最大的组件(或任何其他有趣的指标)。