BFS又名廣度優(yōu)先搜索，和DFS算法一樣都是遞歸算法，不同的是，BFS算法通過隊列，在避免循環(huán)的同時遍歷目標所有節(jié)點。
BFS算法的工作原理圖解
以具有5個節(jié)點的無向圖為例，如下圖：
從節(jié)點0開始，BFS算法首先將其放入Visited列表并將其所有相鄰節(jié)點放入隊列。
接下來，訪問隊列前面的節(jié)點1，并轉到節(jié)點1相鄰的節(jié)點。因為節(jié)點0已經被訪問過，所以訪問節(jié)點2。
節(jié)點2有一個未訪問的相鄰節(jié)點4，但因為節(jié)點4在隊列的最后，因此我們要先訪問位于隊列前面的節(jié)點3。
隊列中只剩下節(jié)點4沒有被訪問，所以最后訪問節(jié)點4。
至此，已經完成了此無向圖的廣度優(yōu)先遍歷。
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代碼實現(xiàn)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)
登錄后復制
