一、Python中什么叫廣度優(yōu)先

廣度優(yōu)先搜索（Breadth First Search，簡(jiǎn)稱(chēng) BFS）是一種基于圖論的搜索算法，用于搜索圖中的節(jié)點(diǎn)。在計(jì)算機(jī)程序中，BFS 可以用于解決諸如迷宮問(wèn)題、八數(shù)碼問(wèn)題、網(wǎng)絡(luò)爬蟲(chóng)等需要對(duì)某種數(shù)據(jù)結(jié)構(gòu)進(jìn)行遍歷的問(wèn)題。

BFS 算法的基本思想是從某一個(gè)起始節(jié)點(diǎn)開(kāi)始，按照寬度優(yōu)先的順序逐層遍歷圖中的所有節(jié)點(diǎn)，直到找到目標(biāo)節(jié)點(diǎn)或者遍歷完整個(gè)圖。在 BFS 算法中，每個(gè)節(jié)點(diǎn)都被標(biāo)記為已訪問(wèn)或未訪問(wèn)。遍歷時(shí)，首先訪問(wèn)起始節(jié)點(diǎn)，然后依次訪問(wèn)與起始節(jié)點(diǎn)相鄰的未訪問(wèn)節(jié)點(diǎn)，并將它們標(biāo)記為已訪問(wèn)。接著，訪問(wèn)這些節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，依次進(jìn)行下去，直到找到目標(biāo)節(jié)點(diǎn)或者遍歷完整個(gè)圖。

在 Python 中實(shí)現(xiàn) BFS 算法可以通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)，首先將起始節(jié)點(diǎn)加入隊(duì)列，然后從隊(duì)列中取出名列前茅個(gè)節(jié)點(diǎn)，并將它的未訪問(wèn)鄰居節(jié)點(diǎn)加入隊(duì)列中。重復(fù)這個(gè)過(guò)程直到找到目標(biāo)節(jié)點(diǎn)或者隊(duì)列為空。

BFS 算法的優(yōu)點(diǎn)在于它能夠保證找到的路徑是最短路徑。因?yàn)?BFS 算法是按照層次順序遍歷節(jié)點(diǎn)的，每一次遍歷都是從距離起始節(jié)點(diǎn)最近的節(jié)點(diǎn)開(kāi)始的，因此找到目標(biāo)節(jié)點(diǎn)時(shí)，一定是經(jīng)過(guò)最少的節(jié)點(diǎn)才能到達(dá)目標(biāo)節(jié)點(diǎn)。