深入解析BFS演算法原理，帶圖解說明，並附帶Python程式碼實作BFS演算法

BFS又稱為廣度優先搜索，和DFS演算法一樣都是遞歸演算法，不同的是，BFS演算法透過佇列，在避免循環的同時遍歷目標所有節點。

BFS演算法的工作原理圖解

以具有5個節點的無向圖為例，如下圖：

從節點0開始，BFS演算法首先將其放入Visited清單並將其所有相鄰節點放入佇列。

接下來，存取佇列前面的節點1，並前往節點1相鄰的節點。因為節點0已經被存取過，所以訪問節點2。

節點2有一個未存取的相鄰節點4，但因為節點4在佇列的最後，因此我們要先存取位於佇列前面的節點3。

佇列中只剩下節點4沒有被訪問，所以最後訪問節點4。

至此，已經完成了此無向圖的廣度優先遍歷。

BFS演算法的偽代碼

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
remove the head u of Q 
mark and enqueue all (unvisited) neighbours of u

Python程式碼實作BFS演算法

import collections
def bfs(graph, root):
    visited, queue = set(), collections.deque([root])
    visited.add(root)

while queue:
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("Following is Breadth First Traversal: ")
    bfs(graph, 0)

以上是深入解析BFS演算法原理，帶圖解說明，並附帶Python程式碼實作BFS演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！