geekdoc-python-zh/docs/py4b/breadth-first-traversal-in-python.md

Python 中的广度优先遍历

原文：https://www.pythonforbeginners.com/data-structures/breadth-first-traversal-in-python

图形是一种非线性数据结构。我们经常使用图形来表示不同的现实世界对象，如地图和网络。在本文中，我们将研究广度优先遍历来打印一个图中的所有顶点。我们还将在 Python 中实现广度优先遍历算法。

什么是广度优先遍历？

广度优先遍历是一种打印图中所有顶点的图遍历算法。在这个算法中，我们从一个顶点开始并打印它的值。然后我们打印当前顶点的所有邻居。之后，我们选择当前顶点的每个邻居，并打印其所有邻居。这个过程一直持续到图形中的所有顶点都被打印出来。

让我们通过在下图中执行广度优先遍历来理解这个过程。

Image of a Graph

假设我们从顶点 a 开始。

打印完顶点 A 后，我们将打印它的所有相邻顶点，即 B、D、E 和 f。

在打印 B、D、E 和 F 之后，我们将选择这些顶点中的一个。让我们选择 d。

由于 D 没有需要打印的邻居，我们将返回到 A 并选择 A 的另一个邻居。

由于 E 没有需要打印的邻居，我们将回到 A 并选择 A 的另一个邻居。

由于 F 没有需要打印的邻居，我们将回到 A 并选择 A 的另一个邻居。

现在，我们将打印 B 的所有尚未打印的邻居。因此，我们将打印 c。

此时，您可以观察到图中的所有顶点都已按 A、B、D、E、F、C 的顺序打印出来。因此，我们将终止该算法。

广度优先遍历算法

使用队列数据结构实现图的深度优先遍历算法。这里，我们假设我们有一个连通图。换句话说，我们可以从起始顶点到达图的每个顶点。

我们将维护一个队列来存储尚未打印的顶点，并维护一个列表来存储已访问的顶点。之后，我们将使用以下算法处理该图。

1. 创建一个空队列 Q 来存储没有被打印的顶点。
2. 创建一个空列表 L 来存储访问过的顶点。
3. 将源顶点插入 Q 和 l。
4. 如果 Q 为空，请转到 9。否则转到 5。
5. 从 q 中取出一个顶点 v。
6. 打印顶点 v。
7. 将 v 的所有不在 L 中的邻居也插入到 Q 和 L 中。
8. 转到第 4 节。
9. 停下来。

可以使用上图中给出的图形的源代码来演示该算法。

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)

def BFS_Algorithm(input_graph, source):
    Q = Queue()
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        print("At:",vertex)
        print("Printing vertex:",vertex)
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                print("At vertex, adding {} to Q and visited_vertices".format(vertex, u))
                Q.put(u)
                visited_vertices.append(u)
        print("visited vertices are: ", visited_vertices)

print("BFS traversal of graph with source A is:")
BFS_Algorithm(graph, "A") 

输出:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
BFS traversal of graph with source A is:
At: A
Printing vertex: A
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
visited vertices are:  ['A', 'B', 'D', 'E', 'F']
At: B
Printing vertex: B
At vertex, adding B to Q and visited_vertices
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: D
Printing vertex: D
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: E
Printing vertex: E
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: F
Printing vertex: F
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: C
Printing vertex: C
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C'] 

在输出中，您可以观察到顶点是按照 A、B、D、E、F 和 c 的顺序打印的。

广度优先遍历在 Python 中的实现

我们已经讨论了图的广度优先遍历的一般思想，并观察了该算法如何使用 python 程序工作，我们可以如下实现广度优先遍历算法。

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)

def BFS(input_graph, source):
    Q = Queue()
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        print(vertex, end= " ")
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                Q.put(u)
                visited_vertices.append(u)

print("BFS traversal of graph with source A is:")
BFS(graph, "A") 

输出:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
BFS traversal of graph with source A is:
A B D E F C 

结论

在本文中，我们讨论了 python 中全连通图的广度优先遍历算法。要了解更多关于其他算法的内容，可以阅读这篇关于 Python 中的有序树遍历的文章。