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

Question

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

因此，我在 python 中实现了一个函数，该函数 returns 为真或为假，具体取决于路径的存在和它是否有效。好吧，它适用于我所做的测试。我想知道的是这是否确实是呼吸优先搜索算法。我以前没有见过任何 BFS 算法，我只知道它的基本思想。我听说 BFS 是递归实现的，虽然我是迭代实现的，这就是为什么我对 it.So 有疑问，这里是我的图形的函数和表示：

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

这是一种 BFS 算法，用于查找路径是否存在，但它不会告诉您该路径是什么，也不会说明您的字典构造以表示图形的方式。

这是上图的 BFS 示例，可以处理字典表示图的方式。找到路径时 returns 路径，不存在路径时返回 False 。如果您只是希望它在找到路径时 return 为真，请将第 19 行编辑为 return True

def BFS2(graph, v1, v2):
    '''
    graph: a dictionary representing an unweighted graph
    v1: a key in graph, representing the start node
    v2: a key and value in graph, representing the end node
    returns: a shortest path from v1 to v2, False if there is no path.
    '''
    if v1 not in graph:
        return False
    path_start = [v1]
    paths = [path_start]
    while len(paths):
        test_path = paths.pop(0)
        last_node = test_path[-1]

        for next_node in graph[last_node]:
            if next_node not in test_path:
                next_path = test_path + [next_node]
                if next_node == v2:
                    paths.append(next_path)
                    return next_path
                elif next_node in graph:
                    paths.append(next_path)
    return False

Answer 2

不，这不是 BFS 算法。 This image will show you how a BFS algorithm would work

Answer 3

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

然而，这也是错误的。 current not in outb 终止条件导致它 wrongly output False for searches like BFS(1, 18), and the while current in parsed: current = toParse.pop(0) loop can exhaust toParse and throw an exception when it tries to pop from an empty list, demonstrated here 的图形略有不同。此外，您的 outb 与它应该表示的图形图片不匹配；它缺少一堆后边，例如 6->4。

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

Is this a breadth-first search algorithm?

python

graph-theory

breadth-first-search