廣度優(yōu)先算法
簡(jiǎn)介
很多問題可以抽象為圖的問題令哟，從圖中尋找某個(gè)點(diǎn)恼琼，最通用的辦法就是暴力窮舉。而廣度優(yōu)先和深度優(yōu)先是兩種常用的遍歷圖的方法屏富。以一個(gè)樹狀圖來說晴竞，廣度優(yōu)先就是從根節(jié)點(diǎn)開始，一層一層的遍歷狠半，下一層的必須等上一層全部遍歷完成才可以被訪問噩死。而以一個(gè)無向圖來舉例的話，通過下面的圖來理解：
- S為起點(diǎn)
- 接下來遍歷 位于同一層次的A,B,C
- 再接下來遍歷下一層次的D
所以順序?yàn)镾,A,B,C,D神年。
詳解
那么具體的思路是什么呢已维？維護(hù)一個(gè)即將訪問的隊(duì)列，這個(gè)隊(duì)列按層次順序存放著即將被訪問的節(jié)點(diǎn)瘤袖。
首先S加入隊(duì)列Q衣摩。
訪問S昂验，同時(shí)將S設(shè)置為已經(jīng)被訪問捂敌。
-
循環(huán)從Q中取出節(jié)點(diǎn)：
- 如果Q為空，則遍歷結(jié)束既琴。
- 如果Q不為空占婉，則類似于S，將該節(jié)點(diǎn)設(shè)置為已經(jīng)訪問甫恩。同時(shí)將其子節(jié)點(diǎn)加入Q進(jìn)行排隊(duì)逆济。要觀察子節(jié)點(diǎn)是否已經(jīng)被訪問或者已經(jīng)加入了隊(duì)列Q，否則將出現(xiàn)死循環(huán)磺箕，或者重復(fù)遍歷奖慌。
用C++實(shí)現(xiàn)
用bfs的方法遍歷用鄰接鏈表表示的圖(這里我用的數(shù)據(jù)結(jié)構(gòu)為嵌套的vector)：
void BFS(vector<vector<int>> topo) { //鄰接鏈表
deque<int> Q; //即將訪問
vector<int> P; //已經(jīng)訪問
Q.push_back(0); //加入初始節(jié)點(diǎn)
while (!Q.empty()) {
int temp = Q.front();
Q.pop_front();
cout << temp << " "; //取出并訪問該節(jié)點(diǎn)
P.push_back(temp); // 加入已經(jīng)訪問集合
for (auto each : topo[temp]) {
if (find(P.begin(), P.end(), each) != P.end()
|| find(Q.begin(), Q.end(), each) != Q.end()) //確保還沒有被訪問
continue;
Q.push_back(each);
}
}
}
注意：在添加子節(jié)點(diǎn)到Q隊(duì)列時(shí)，要保證子節(jié)點(diǎn)沒有被訪問且還沒有在Q隊(duì)列中松靡〖蛏可以使用數(shù)組置位O(1)的方法來表示，我這樣通過find函數(shù)反而浪費(fèi)了時(shí)間雕欺。
剪枝和分支限界
BFS實(shí)際上是一種暴力的窮舉策略岛马，會(huì)花費(fèi)很大的時(shí)間棉姐，有時(shí)候需要通過剪枝和分支限界來減少不必要的訪問：
剪枝：在訪問某一節(jié)點(diǎn)時(shí)，發(fā)現(xiàn)該節(jié)點(diǎn)以及其所有子節(jié)點(diǎn)必然不會(huì)存在可行最優(yōu)解啦逆，則跳過該節(jié)點(diǎn)以及其子節(jié)點(diǎn)伞矩。這樣的優(yōu)化策略稱之為剪枝。
實(shí)戰(zhàn)
最近刷算法題目夏志，做到POJ-1753乃坤。用到了BFS方法。而做具體問題的時(shí)候盲镶，并不會(huì)像我們學(xué)習(xí)BFS時(shí)有一個(gè)明顯存在著的等待被遍歷的圖侥袜，而是需要自己去構(gòu)造。有時(shí)更像是在遍歷一個(gè)虛擬的圖溉贿。
有時(shí)候需要遍歷的是一個(gè)又一個(gè)的狀態(tài)枫吧，一個(gè)狀態(tài)可以衍生出幾個(gè)子狀態(tài)或者是一個(gè)狀態(tài)可以推到出其它的幾個(gè)狀態(tài)，這個(gè)時(shí)候我們也可以使用BFS宇色，具體方法與遍歷圖一樣九杂，只不過是將從當(dāng)前狀態(tài)推到出的狀態(tài)加入隊(duì)列Q即可，而避免狀態(tài)的重復(fù)/循環(huán)遍歷是一個(gè)需要著重考慮的問題宣蠕。
