algorithm - 有人可以解释广度优先搜索吗？

Question

有人可以解释广度优先搜索来解决以下问题吗

我需要找到 4 到 7 之间的所有路径

Answer 1

您查看与起始节点相邻的所有节点。然后您查看与这些节点相邻的所有节点（不返回您已经查看过的节点）。重复直到找到满意的节点或没有更多的节点。

对于您指出的那种问题，您使用上述过程构建一组路径，终止到达所需目标节点的任何路径，并且当您的图表用尽时，这样终止的路径集就是您的解决方案集。

Answer 2

广度优先搜索 (BFS) 意味着您在进入更深层次之前处理所有起始节点的直接子节点。BFS 是通过一个队列实现的，该队列存储需要处理的节点列表。

通过将起始节点添加到队列中来启动算法。然后你继续运行你的算法，直到队列中没有任何东西需要处理。

当您从队列中取出一个元素时，它将成为您的活动节点。在处理活动节点时，将其所有子节点添加到队列的后面。当您有一个空队列时，您终止算法。

由于您处理的是图形而不是树，因此您需要存储已处理节点的列表，这样您就不会进入循环。

到达节点 7 后，您就有了匹配的路径，您可以停止对该递归路径执行 BFS。这意味着您根本不将其子项添加到队列中。为了避免循环并知道您访问过的确切路径，在您进行递归 BFS 调用时，请传递已经访问过的节点。

Answer 3

将其视为带有指向其他网站的链接的网站。让 A 成为我们的根节点或我们的起始网站。

A 是起始页（第 1 层）
A 链接到 AA、AB、AC（第 2 层）
AA 链接到 AAA、AAB、AAC（第 3 层）
AB 链接到 ABA、ABB、ABC（第 3 层）
AC 链接到 ACA、ACB、ACC（第 3 层）

这只有三层深。您一次搜索一层。因此，在这种情况下，您将从 A 层开始。如果不匹配，则转到下一层，AA、AB 和 AC。如果这些网站都不是您要搜索的网站，那么您可以点击链接并转到下一层。换句话说，你一次只看一层。

您将从 A 到 AA 到 AAA 进行深度优先搜索（其补充）。换句话说，你会在去宽之前先去深。

Answer 4

您测试连接到根节点的每个节点。然后您测试连接到先前节点的每个节点。以此类推，直到找到答案。

基本上，每次迭代都会测试与根节点距离相同的节点。

Answer 5

开始

4；

4,2;

4,2,1; 4,2,3; 4,2,5;

4,2,1;（失败）4,2,3,6; 4,2,5,6; 4,2,5,11;

4、2、3、6、7；（通过）4、2、3、6、8；4,2,5,6,7；（通过）4,2,5,6,8；4,2,5,11,12;

4,2,3,6,8,9; 4,2,3,6,8,10; 4,2,5,6,8,9; 4,2,5,6,8,10; 4、2、5、11、12；（失败）

4,2,3,6,8,9;(失败) 4,2,3,6,8,10;(失败) 4,2,5,6,8,9;(失败) 4,2,5 ,6,8,10;（失败）

结尾