圖文解析圖論BFS（廣度優(yōu)先搜索）

97693 閱讀 0 評(píng)論 0 點(diǎn)贊

BFS 全稱是 Breadth First Search，中文名是寬度優(yōu)先搜索，也叫廣度優(yōu)先搜索。是圖上最基礎(chǔ)、最重要的搜索算法之一。

所謂寬度優(yōu)先。就是每次都嘗試訪問同一層的節(jié)點(diǎn)。如果同一層都訪問完了，再訪問下一層。這樣做的結(jié)果是，BFS 算法找到的路徑是從起點(diǎn)開始的最短合法路徑。換言之，這條路徑所包含的邊數(shù)最小。

在 BFS 結(jié)束時(shí)，每個(gè)節(jié)點(diǎn)都是通過從起點(diǎn)到該點(diǎn)的最短路徑訪問的。

（1）我們可以用比喻來說明廣度優(yōu)先搜索算法

● 在一片草木枯黃的深秋草原上，在草原的某一處出現(xiàn)了一處野火

● 一開始的時(shí)候野火集中于一點(diǎn)之上，在這點(diǎn)野火耗盡當(dāng)前植被變成灰燼之前點(diǎn)燃了周圍的植被

● 比如節(jié)點(diǎn)s是初始火種，假設(shè)我們手中有一個(gè)秒表，每過1秒，我們的大火會(huì)向外邁進(jìn)一步

● 這個(gè)過程只能向外，不能向內(nèi)，因?yàn)橹荒茳c(diǎn)燃植被，不能把灰燼點(diǎn)燃

● 藍(lán)色的點(diǎn)是即將變?yōu)榛覡a的點(diǎn)，紅色的點(diǎn)是剛被點(diǎn)燃的點(diǎn)，灰色的圓形或圓角矩形是一個(gè)前鋒面

● 所謂前鋒面是火焰向外傳播的一個(gè)面，frontier

● 之后，每一處的植被都按照同樣的模型向外去蔓延, 點(diǎn)燃外層的鄰居，前鋒面越來越大，最終整個(gè)草原燃燒殆盡

● 這個(gè)過程是非常自然的，也就是所謂的道法自然，模擬自然的一個(gè)過程

● 整個(gè)過程，如下圖所示

寬度優(yōu)先搜索

● 任何圖結(jié)構(gòu)的模型，只要指定一個(gè)節(jié)點(diǎn)，比如上圖中的s點(diǎn)作為"樹根"

● 我們可以把整棵樹(圖)攤平在某個(gè)桌面上，接下來就要開始進(jìn)行模擬計(jì)算

● 如果一個(gè)點(diǎn)自己是點(diǎn)燃狀態(tài)的，那么它接下來就通過一個(gè)邊去點(diǎn)燃外部的鄰居

● 如果鄰居是灰燼狀態(tài)不會(huì)被點(diǎn)燃(不會(huì)向內(nèi)部傳播)，就是這個(gè)過程可以點(diǎn)燃整片草原

● 這個(gè)方法可以針對s點(diǎn)而言可達(dá)的，連通的部分全部訪問一遍，這種訪問的特點(diǎn)是不重不漏

● 這個(gè)方法被稱為遍歷，也就是traverse或traversal

算法框架實(shí)現(xiàn)

template <typename Tv, typename Te>

// v是初始點(diǎn)，clock是讀秒器或稱為計(jì)時(shí)器
void Graph<Tv, Te>::BFS(int v, int & clock) {
    // 1. 初始化
    // 1.1 內(nèi)部引入一個(gè)隊(duì)列Q, 任何一個(gè)點(diǎn)，初始化的時(shí)候都是UNDISCOVERED狀態(tài)，初始的時(shí)候v指定為DISCOVERED狀態(tài)
    // 1.2 換種說法：UNDISCOVERED是未燃燒狀態(tài)，DISCOVERED是燃燒狀態(tài)
    // 1.3 初始點(diǎn)入隊(duì)
    Queue<int> Q; status(v) = DISCOVERED; Q.enqueue(v);
    // 2. 處理當(dāng)前的前鋒面上的所有元素
    // 2.1 進(jìn)行循環(huán)處理, 循環(huán)終止條件是隊(duì)列變空, 也就是燃燒殆盡
    while(!Q.empty()) {
        // 反復(fù)地，如果不空, FIFO, 并且添加一個(gè)時(shí)間標(biāo)簽，這里的dTime, d暗示DISCOVERED
        // 這時(shí)候一個(gè)元素獨(dú)立的占據(jù)1s，其實(shí)同一個(gè)前鋒面上的點(diǎn)在自然環(huán)境中是同時(shí)燃燒的
        // 因?yàn)槲覀儧]法做到, 所以為每一個(gè)元素添加一個(gè)時(shí)間標(biāo)簽，這是一種蹩腳的體現(xiàn)
        int v = Q.dequeue(); dTime(v) = ++clock; // 取出隊(duì)首頂點(diǎn)v
        // 考察v的每一鄰居u，這個(gè)for循環(huán)是這個(gè)v點(diǎn)的使命，-1<u, 表示u不再是鄰居了
        for(int u = firstNbr(v); -1 < u; u = nextNbr(v,u)) {
            // 根據(jù)u的狀態(tài)，分別處理
            if(UNDISCOVERED == status(u)) {
                // 若u尚未被發(fā)現(xiàn)，則
                status(u) = DISCOVERED; // 當(dāng)前鄰居標(biāo)記成DISCOVERED狀態(tài)
                Q.enqueue(u); // 發(fā)現(xiàn)該頂點(diǎn)，將該鄰居入隊(duì)尾，進(jìn)入前鋒面的范圍
                type(v,u) = TREE; // u之所以會(huì)燒起來是被內(nèi)部的鄰居v點(diǎn)燃的, 在將來生成的樹中，火傳遞的方向?qū)?yīng)的就是邊, 引入樹邊TREE EDGE
                parent(u) = v; // u要把v作為自己的parent
            } else {
                // 若u已被發(fā)現(xiàn)(正在隊(duì)列中)，或者已經(jīng)能訪問完畢(已出隊(duì)列),將(v,u)歸類于跨邊
                type(v,u) = CROSS;
            }
        }
        // 2.2. 此時(shí)，當(dāng)前頂點(diǎn)訪問完畢，也就是v變成了灰燼并且處理完成v所有的鄰居
        status(v) = VISITED;
    }
}

● 代碼實(shí)現(xiàn)可以有很多風(fēng)格，每種都會(huì)有細(xì)微的差異，這里的算法是基于c++模板構(gòu)成的

● 這個(gè)算法是模擬自然的過程，最重要的模擬是如何模擬前鋒面

● 只要我們模擬出了前鋒面(一圈一圈的，一個(gè)單位時(shí)間，對應(yīng)一個(gè)半徑的增長)，就模擬出了整個(gè)燃燒的過程

● 目前，我們沒有什么好的并行機(jī)制，將任何時(shí)候的前鋒面模擬出來，我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)

● 我們需要把所有前鋒面上的所有點(diǎn)都收容進(jìn)去，但是我們不可能理想的并行的去模擬

● 實(shí)際上，前鋒面上的每個(gè)火源都是各向同性，互不干擾，高效地往外傳遞，但是我們的計(jì)算必須要一個(gè)點(diǎn)一個(gè)點(diǎn)的處理

● 這些前鋒面上的火源表面上看都是相等的，但是我們需要人為的指定一個(gè)優(yōu)先級(jí)，比如指定一個(gè)點(diǎn)A

● 在處理這個(gè)點(diǎn)A的時(shí)候，我們要模擬它在燃燒模型中的行為，它的外層鄰居如：A1′,A2′,A3′...將被點(diǎn)燃

● 這個(gè)時(shí)候就有意思了，當(dāng)它的這些外層鄰居都點(diǎn)燃了, 點(diǎn)A就會(huì)成為灰燼，就可以被刪除了

● 而且理想模型下的點(diǎn)A的同輩：B,C,D…這些在前鋒面上的同輩兄弟節(jié)點(diǎn)都沒有了，都可以被刪除了

● 這個(gè)時(shí)候，就形成了第二個(gè)前鋒面，但是這個(gè)理想型的并發(fā)模型，我們無法實(shí)現(xiàn)

● 所以，當(dāng)點(diǎn)A變成灰燼之時(shí)，就可以組織第二個(gè)前鋒面了，我們讓點(diǎn)A的外層鄰居先進(jìn)來