在Python中的广度优先搜索|极客笔记

在Python中的广度优先搜索

在Python中，广度优先搜索和深度优先搜索技术被用于搜索树或图。这两个技术对于每个新的Python编程人员来说都是最关键的主题之一。我们将讨论广度优先搜索在Python中的具体定义，它的算法是如何工作的，如何用示例代码来实现它，以及结果。我们还将了解BFS广度优先搜索的现实世界应用和使用方法。

什么是广度优先搜索

广度优先搜索（BFS）是一种搜索图或树的方法，正如前面提到的那样。遍历树意味着访问每个节点。广度优先搜索是一种递归方法，用于搜索树或图的所有节点。在Python中，我们可以利用列表或元组等数据结构来执行BFS。在树和图中，广度优先搜索几乎是相同的。唯一的区别是树可能有循环，这将使我们能够重新访问相同的节点。

BFS算法

在学习如何编写Python代码之前，让我们先了解一下广度优先搜索使用的方法，并讨论其输出。以魔方为类比来说明。魔方被认为是寻找一种将其从一堆颜色混乱变成单一颜色的方法。当将魔方与树或图进行比较时，可以得出结论，魔方的可能状态与我们网络的顶点相关，魔方的可能动作与图的边相关。

广度优先搜索算法遵循以下步骤。

首先，在队列的下端放置我们图中的任一顶点。
将创建的队列中的第一个元素添加到已检查过的对象列表中。
创建一个列表，列出与该顶点相邻的所有节点。将不在访问列表中的个别节点移动到队列的尾部。
重复上述两个步骤，即步骤2和步骤3，直到我们的队列减少到0。

由于广度优先搜索遍历给定图的每个节点，标准BFS算法将树或图的每个节点或顶点分为两个不同的组。

已访问
未访问

所讨论的技术的目标是在访问每个顶点的同时避免重复循环。BFS从一个节点开始，然后检查所有距离内的节点，然后在两个距离下的所有其他节点，依此类推。为了保留尚未访问的节点，BFS需要一个队列（或在Python中为列表）。

代码

# Python code to give the traversed path by BFS algorithm as output. BFS(int n) scans through the vertices which are reachable from n.
from collections import defaultdict as dd

class Graph:

    # Constructing a list
    def __init__(self):

        # default dictionary to store graph
        self.graph = dd(list)

    # defining function which will add edge to the graph
    def addEdgetoGraph(self, x, y):
        self.graph[x].append(y)

    # defining function to print BFS traverse
    def BFSearch(self, n):

        # Initially marking all vertices as not visited
        visited_vertices = ( len(self.graph ))*[False]

        # creating a queue for visited vertices
        queue = []

        # setting source node as visited and adding it to the queue
        visited_vertices[n] = True
        queue.append(n)


        while queue:

            # popping the element from the queue which is printed
            n = queue.pop(0)
            print (n, end = " ")

            # getting vertices adjacent to the vertex n which is dequed. 
            for v in self.graph[ n ]:
                if visited_vertices[v] == False:
                    queue.append(v)
                    visited_vertices[v] = True


# Example code
# Initializing a graph
graph = Graph()
graph.addEdgetoGraph(0, 1)
graph.addEdgetoGraph(1, 1)
graph.addEdgetoGraph(2, 2)
graph.addEdgetoGraph(3, 1)
graph.addEdgetoGraph(4, 3)
graph.addEdgetoGraph(5, 4)

print ( " The Breadth First Search Traversal for The Graph is as Follows: " )
graph.BFSearch(3)

输出：

The Breadth First Search Traversal for The Graph is as Follows: 
3 1

我们首先在上述Python程序中生成了图形，然后我们应用了广度优先搜索方法。之后，我们初始化了两个列表：一个用于跟踪BFS算法访问过的图节点，另一个用于跟踪队列中的节点。

我们声明了一个带有visited节点、图本身和上述步骤的节点作为参数的函数。我们必须在函数内部不断添加visited_vertices和queue列表。

然后程序将在尚未访问的节点队列上执行while循环，然后删除并显示当前节点所访问的节点。最后，我们使用for循环来查找未访问的节点，并将它们添加到visited_vertices和queue列表中。然后，我们用参数调用BFSearch函数，该参数是我们在输出中想要的第一个节点。

时间复杂度

广度优先搜索算法的时间复杂度为O(V+E)，其中V表示节点数，E表示边数。此外，BFS算法的空间复杂度为O(V)。

广度优先遍历的应用

最短路径和最小距离： 在无权图中，最短路径是边最少的路径。使用广度优先时，通常使用最少的边从源节点到达一个节点。对等网络（P2P）广度优先常用于发现BitTorrent等对等网络中所有邻居节点。
搜索引擎的爬虫： 爬虫通过从广度到深度创建索引。目标是从根页面开始，探索所有链接。
社交网络网站： 我们可以使用广度优先搜索来识别社交关系中距离某个成员m级的人。
在GPS导航设备中，使用广度优先搜索来找到附近的所有地点。
广播数据包使用广度优先搜索算法在网络中到达所有节点。
在垃圾收集中，使用BFS（广度优先搜索）通过Cheney技术来复制垃圾编译。
在无向网络中，可以通过广度优先搜索或DFS（深度优先搜索）来实现循环的识别。在有向网络中，也可以使用BFS来找到循环。
Ford-Fulkerson算法： 为了确定Ford-Fulkerson方法中的最优流，我们可以使用广度优先或深度优先遍历。但是，使用广度优先遍历会将最坏情况的时间复杂度降低到O(VE^2)。发现路径以查看是否存在连接两个节点的路径，我们可以使用广度优先或深度优先遍历。