Java顺序BFS

Question

我目前正在优化我的代码。为了做到这一点，我必须确保我的顺序BFS完美地工作。然后，我应该应用线程或executor服务并行运行它。如果图形太大，我的BFS会崩溃吗？

public void bfs(int rootNode, isvisited visitor)
{
// BFS uses Queue data structure
Queue<Integer> q = new LinkedList<Integer>();
int currentLevel = 0;

q.add(rootNode);
visitor.visit(rootNode, currentLevel);

while (!q.isEmpty())
{
    currentLevel++;
    Set<Integer> nextNodes = new LinkedHashSet<Integer>();
    q.forEach(currNode ->nextNodes.addAll(outgoingNeighbors(currNode)));
    q.clear();

    for (int child : nextNodes) 
    {
        visitor.visit(child, currentLevel);
        q.add(child);
    }
} }

Answer 1

..。为了做到这一点，我必须确保我的顺序BFS完美地工作。..。

你有没有试过写一些单元测试来证明或否定这个功能？总的来说，对我来说，它看起来很好，尽管它真的取决于visitor.visit(...)做什么。另外，还不清楚outgoingNeighbors是干什么的。

次要评论：

• q.forEach(currNode ->nextNodes.addAll(outgoingNeighbors(currNode)));缺少一个空格
• for (int child : nextNodes)...也可以使用forEach。
• 如果您去队列而不是执行forEach，则不应该在结束时执行清除操作。

..。我应该应用线程或executor服务并行运行它。

当使用多线程时，我的建议是总是把事情分解成不依赖的任务。目前，“访客”对象似乎有点可疑，并可能导致未来的麻烦。

你有做多线程的代码吗？

如果图形太大，我的BFS会崩溃吗？

好的。如果您的意思是您可以调用一个1000个节点的东西，应该是好的。如果您计划在chromebook上创建100万个线程，您可能会遇到一些问题。这真的取决于你对大的定义和你正在使用的限制。

请注意，规模问题通常通过优化代码/解决方案或以分布式方式解决问题来解决。如果您开始遇到这样的问题，我建议您从调试器开始，找出问题所在，然后开始为您发现的任何问题找到一个很好的解决方案。

Answer 2

既然Rishi已经解决了您的问题，那么让我来谈谈您的代码：

1. 大多数java编码约定的开头大括号都与块导入器相同: public void (int rootNode，visitor访问者){
2. 类型应该以大写字母开头。因此，它是IsVisited。尽管如此，这整件事对我来说还是很可疑的。字体名称很奇怪。通常，is-prefix是为布尔人保留的。因此，该类型可能更好地命名为BFSVisitor或类似于这些代码的名称。
3. 没有必要将变量名缩短为单个字母：q应该是queue
4. 您完全忽略了遍历图中循环的可能性。队列不知道已经访问过的节点，因此可以多次访问它们，从而导致无限循环。，您可以通过跟踪访问了多少节点，并在访问图中的所有节点(或进入循环)时中断循环来弥补这一问题。
5. 你在这里做的穿越看起来真的很奇怪。标准的BFS遍历可以通过一个队列完成。您使用两个，其中一个被用作遍历中的“下一个级别”的中间存储，它只是将节点添加回原始队列。，这似乎是因为限制跟踪当前的遍历级别。如果您能够取消该限制，代码将自动变得更快。
6. “不正确”使用羔羊。为了准备下一个级别，请考虑如下内容: queue.stream().flatMap(this::outgoingNeighbors) .forEach( nextNodes ::add)；只要稍微眯一下眼，我们就可以看到以下简化: Set nextNodes= queue.stream() .flatMap(这里:outgoingNeighbors) .collect(Collectors.toSet())；注意，这应该已经消耗了队列中的元素。clear()应该是不必要的。
7. 既然您显然被允许使用流，那么下面的附加简化如何:nextNodes.forEach(子-> {visitor.visit，currentLevel)；queue.add(子)；}；