python - 这是广度优先搜索算法吗？

Question

所以，我有这个图，我想使用广度优先搜索算法来查看是否存在从一个顶点到另一个顶点的路径。

因此，我在 python 中实现了一个函数，它根据路径是否存在返回 true 或 false，并且它可以工作。嗯，它对我所做的测试有效。我想知道这是否确实是呼吸优先搜索算法。我以前没有见过任何BFS算法，我只知道它的基本思想。我听说 BFS 是递归实现的，尽管我是迭代实现的，这就是我对此有疑问的原因。所以，这里是我的图的函数和表示:

outb = {1: [2, 3],
  2: [4, 5],
  3: [5, 11, 12],
  4: [6, 7],
  5: [7],
  6: [9, 10],
  7: [8],
  11: [3],
  12: [15, 14, 13],
  13: [17],
  14: [17],
  15: [12, 5, 8, 16],
  17: [18]}

def BFS(v1, v2):
    parsed = []
    toParse = [v1]
    current = v1

    while len(toParse) > 0:

        while current in parsed:
            current = toParse.pop(0)

        if current not in outb:
            return False

        if v2 in outb[current]:
            return True

        toParse += outb[current]
        parsed.append(current)

    return False

我的最后一个问题是:BFS 本质上是找到从一个顶点到另一个顶点的最短路径吗？我在互联网上读到了这篇文章，我想确定一下。

Answer 1

这是广度优先搜索。它遵循相当典型的结构，将搜索边界视为队列(尽管列表对于队列来说是一个低效的选择)，并且它按照距根的距离顺序考虑节点，就像标准的广度优先搜索一样。

但是，这也是错误的。 current not in outb 终止条件导致其 wrongly output False对于诸如 BFS(1, 18) 之类的搜索，以及 while current in parsed: current = toParse.pop(0) 循环可能会耗尽 toParse并在尝试从空列表 demonstrated here 中弹出时抛出异常与略有不同的图表。此外，您的 outb 与它应该表示的图表图片不匹配；它缺少一堆后边缘，例如 6->4。