【技術(shù)分享】圖遍歷算法之廣度優(yōu)先遍歷算法

廣度優(yōu)先遍歷算法應(yīng)用的是隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，它的遍歷過程如下：

（1）以圖中的任一頂點(diǎn)V為出發(fā)點(diǎn)，首先訪問頂點(diǎn)V。

（2）訪問頂點(diǎn)V的所有未被訪問過的鄰接點(diǎn)V 1 ，V 2 ，……，V n 。

（3）按照V 1 ，V 2 ，……，V n 的次序，訪問每個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)。

（4）以此類推，直到圖中所有和頂點(diǎn)V連通的頂點(diǎn)都被訪問過為止。

這里以下圖所示的無向圖為例來介紹此方法的遍歷過程。

步驟1 ：假設(shè)以頂點(diǎn)A為起點(diǎn)，將頂點(diǎn)A放入隊(duì)列，如下圖所示。

步驟2 ：取出頂點(diǎn)A，將頂點(diǎn)A的鄰接點(diǎn)B和C放入隊(duì)列，如下圖所示。

步驟3 ：根據(jù)隊(duì)列“先進(jìn)先出”的原則，取出頂點(diǎn)B，將與頂點(diǎn)B相鄰并且未被訪問過的頂點(diǎn)D和頂點(diǎn)E放入隊(duì)列，如下圖所示。

步驟4 ：取出頂點(diǎn)C，將與頂點(diǎn)C相鄰并且未被訪問過的頂點(diǎn)F放入隊(duì)列，如下圖所示。

步驟5 ：取出頂點(diǎn)D，將與頂點(diǎn)D相鄰并且未被訪問過的頂點(diǎn)放入隊(duì)列。由于頂點(diǎn)D的鄰接點(diǎn)B和E都已被訪問過，所以無需放入隊(duì)列中，如下圖所示。

步驟6 ：取出頂點(diǎn)E，將與頂點(diǎn)E相鄰并且未被訪問過的頂點(diǎn)放入隊(duì)列。由于頂點(diǎn)E的四個(gè)鄰接點(diǎn)都已被訪問過，所以無需放入隊(duì)列中，如下圖所示。

步驟7 ：取出頂點(diǎn)F，將與頂點(diǎn)F相鄰并且未被訪問過的頂點(diǎn)放入隊(duì)列。由于頂點(diǎn)F的鄰接點(diǎn)C和E都已被訪問過，所以無需放入隊(duì)列中，如下圖所示。

此時(shí)，隊(duì)列中的值都已被取出，表示圖中的頂點(diǎn)都已被訪問過。由此可知，本例中進(jìn)行廣度優(yōu)先遍歷的順序?yàn)椋喉旤c(diǎn)A、頂點(diǎn)B、頂點(diǎn)C、頂點(diǎn)D、頂點(diǎn)E、頂點(diǎn)F。

用Python代碼描述上述過程，則算法代碼如下：

def  bfs (graph, start):

    queue = [] #  定義隊(duì)列

     queue.append(start) #  將起始頂點(diǎn)放入隊(duì)列

     visited =  set () #  定義集合

     visited.add(start) #  將起始頂點(diǎn)放入已訪問集合

     while  queue:

        vertex = queue.pop(0) #  取出隊(duì)列第一個(gè)元素

         print (vertex, end  =  ' ' ) #  打印廣度優(yōu)先遍歷的頂點(diǎn)

         for  w  in  graph[vertex] : #  遍歷相鄰的頂點(diǎn)

             if  w  not in  visited: #  如果該頂點(diǎn)未被訪問過

                visited.add(w) #  將該頂點(diǎn)放入已訪問集合

                 queue.append(w) #  把頂點(diǎn)放入隊(duì)列