亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

BFS又名廣度優(yōu)先搜索，和DFS算法一樣都是遞歸算法，不同的是，BFS算法通過(guò)隊(duì)列，在避免循環(huán)的同時(shí)遍歷目標(biāo)所有節(jié)點(diǎn)。

BFS算法的工作原理圖解

以具有5個(gè)節(jié)點(diǎn)的無(wú)向圖為例，如下圖：

從節(jié)點(diǎn)0開(kāi)始，BFS算法首先將其放入Visited列表并將其所有相鄰節(jié)點(diǎn)放入隊(duì)列。

接下來(lái)，訪問(wèn)隊(duì)列前面的節(jié)點(diǎn)1，并轉(zhuǎn)到節(jié)點(diǎn)1相鄰的節(jié)點(diǎn)。因?yàn)楣?jié)點(diǎn)0已經(jīng)被訪問(wèn)過(guò)，所以訪問(wèn)節(jié)點(diǎn)2。

節(jié)點(diǎn)2有一個(gè)未訪問(wèn)的相鄰節(jié)點(diǎn)4，但因?yàn)楣?jié)點(diǎn)4在隊(duì)列的最后，因此我們要先訪問(wèn)位于隊(duì)列前面的節(jié)點(diǎn)3。

隊(duì)列中只剩下節(jié)點(diǎn)4沒(méi)有被訪問(wèn)，所以最后訪問(wèn)節(jié)點(diǎn)4。

至此，已經(jīng)完成了此無(wú)向圖的廣度優(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

登錄后復(fù)制

Python代碼實(shí)現(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)

登錄后復(fù)制