广度优先搜索算法实现函数

广度优先搜索算法（BFS）是一种用于图或树的遍历和搜索的算法。它从根节点开始，逐层遍历，直到找到目标节点或遍历完整个图或树的所有节点。

BFS使用队列来保存待访问的节点，初始时将根节点放入队列中。然后从队列中取出一个节点，访问该节点，并将其未访问过的邻居节点加入队列。重复这个过程，直到队列为空。

下面是一个用Python实现BFS算法的函数：

def BFS(graph, start, target):
    queue = []
    visited = set()
    queue.append(start)
    visited.add(start)
    
    while queue:
        node = queue.pop(0)
        if node == target:
            return True
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
    
    return False

该函数接受三个参数：图graph，起始节点start和目标节点target。图以字典的形式表示，键是节点，值是与该节点直接相连的节点列表。函数使用一个队列来保存待访问的节点，还使用一个集合visited来保存已经访问过的节点。

函数首先将起始节点加入队列，并标记为已访问。然后进入一个循环，直到队列为空。在循环中，函数从队列中取出一个节点，将其与目标节点进行比较。如果相等，则找到目标节点，返回True。否则，函数将该节点的未访问过的邻居节点加入队列，并标记为已访问。

如果循环结束后仍未找到目标节点，则返回False。

需要注意的是，BFS算法的时间复杂度是O(V+E)，其中V是节点的数量，E是边的数量。这是因为每个节点最多访问一次，并且每条边最多访问一次。

使用这个BFS函数可以在图或树中搜索特定的节点，也可以用来解决一些与搜索相关的问题，如迷宫问题、查找图的最短路径等。