本文有以下內容:
廣度優先搜索的描述
廣度優先搜索的優點
3. 廣度優先搜索的代碼模版
描述:
廣度優先搜索算法用于樹的遍歷。算法的描述概括如下:
取得當前節點
將當前節點入隊列
當隊列不為空時，獲得隊頭節點head，隊頭head出隊列；
判斷隊頭的狀態是否是待求狀態
是，則作相應處理；結束算法
不是，將head的所有滿足條件的子節點入隊列，返回步驟II
廣度優先搜索的優點:
廣度優先搜索算法的適用于最短路徑之類的問題，由于該算法對狀態樹的遍歷是遵從層序遍歷的，所以總是可以保證先找到的是最優的。此外，該算法的在處理某些特殊情況時，需要調整數據結構，調整的方式大致為改隊列為優先隊列、更改節點的數據結構(如:添加一些變量來對狀態進行判斷)等；具體的修改方式隨需求而變。
廣度優先搜索算法的代碼模版
void bfs(int x,int y)
{
node in,out;//此處node為當前節點的數據結構
queue<node> q;//此處的queue是C++STL中的容器queue
//當前節點入隊列
in.x=x;in.y=y;
q.push(in);
//判斷當前隊列是否為空
while(!q.empty())
{
out=q.front();//取得當前隊列的隊頭
q.pop();//將隊頭出隊列
if(隊頭滿足條件)
{
//作相應處理
reutrn ;
}
else
{
while(當前節點out有子節點)
{
//獲得當前節點out的滿足條件的子節點
//將該子節點入隊列
}
}
}
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
