算法競賽學習周記——廣度優先搜尋（BFS）

什麼是廣搜

廣搜，即廣度優先搜尋，是一種基于隊列這種資料結構的搜尋算法。

隊列

即先進先出表隊列主要涉及兩種操作，出隊和入隊。在模拟這兩種操作時，要設兩個指針head和tail，指代隊首和隊尾。

head:指向隊首的前一個元素

tail:指向隊尾元素

當head=2，tail=4時，隊列中共有4-2=2個元素。同理，每時每刻隊列中共有tail-head個元素（以下head簡稱h，tail簡稱t）

出隊：++h;//後移一位，相當于隊首後移一位

入隊：++t；que[t]=val;//val值入隊，隊尾向後移一個位置。

實質

廣搜即通過隊列反複入隊出隊的過程。

廣搜模闆

void bfs(所傳參數)
{
	隊列初始化，起點入隊
	while(h<t)//判斷隊列是否非空
	{
		++h//出隊
		for(   )//節點擴充規則
			if(能擴充出節點&&該點未被其他節點擴充時通路)
			{
				++t;//元素準備入隊
				入隊，在隊列中儲存結果
				if（該點為目标節點）
				{
					處理結果
					h=t;//準備退出
					break;
				}
			}
	}
}
           

廣搜路徑列印

廣搜是通過記錄前驅結點，最後順藤摸瓜實作列印路徑的。設pre[] 數組，用來記錄前驅結點。當擴充出

一個結點時，記錄：pre[t]=h 。是隊列中的編号。

廣搜連通塊問題

同DFS的搜尋機制相似，擴充節點并标記，雙層for循環周遊二維數組，同時記錄調用函數的次數。

廣搜與深搜的比較

1.dfs基于遞歸，bfs基于隊列。

2.dfs是“一條路走到底”，bfs是“地毯式搜尋”。

3.dfs的時間複雜度很高，往往需要剪枝。bfs首次搜到的是最優解，但是對空

間的要求高（主要是隊列需要空間）。

4.dfs 适用于求出所有解，bfs 适用于求出最優解。有時還需要對dfs求出的所有

解進行比較，确定一個最優解，但利用dfs求最優解，時間複雜度高。

5.dfs和bfs都是非常優秀的搜尋算法，更要多加練習。