019-dfs.bfs-圖的遍歷-《算法設計技巧與分析》M.H.A學習筆記
來源：程序員人生 發布時間：2016-07-14 14:44:59 閱讀次數：2655次
深度優先搜索DFS
深搜框架:
bool dfs(int loc) {
標記狀態loc已訪問;
if (loc為目標狀態) return true;
for (每一個可能的操作) {
對loc利用操作產生新狀態nstat;
if (nstat合法且未被訪問) {
if (dfs(nstat)) return true;
}
}
撤消loc已訪問標記; // 這步要具體問題具體分析了
return false;
}
廣度優先搜索BFS
實現方法
1. 首先將根節點放入隊列中。
2. 從隊列中取出第1個節點，并檢驗它是不是為目標。
· 如果找到目標，則結束搜索并回傳結果。
· 否則將它所有還沒有檢驗過的直接子節點加入隊列中。
3. 若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜索的目標。結束搜索并回傳“找不到目標”。
4. 重復步驟2。
廣搜框架：
<pre name="code" class="cpp">bool bfs(int init) {
que.enque(init);
while (隊列que不是空的) {
int loc = que.front(); que.deque();
if (loc是目標狀態) return true;
for (每一個可能的操作) {
對loc利用操作產生新狀態nstat;
if (nstat合法且未入隊) {
標記nstat已入隊;
que.enque(nstat);
}
}
}
return false;
}
補充：
簡化代碼：
在1類搜棋盤、搜地圖、搜矩陣位置的問題中我們會頻繁遇到“從當前點獲得相鄰點”的操作，為了縮短代碼，我們可以開個方向數組dir[][2]表示方向，以4方向為例，則dir[4][2]
= {{0, 1}, {1, 0}, {0, 1}, {⑴, 0}};
用的時候有：
for (int i = 0; i < 4; ++i)
{
int newX = oldX + dir[i][0];
int newY = oldY + dir[i][1];
if (newX,newY均合法且未訪問) // bfs或dfs的相干操作
}
記錄路徑：
廣搜：
如果題目需要我們記錄解路徑，則對廣搜有：
struct TStat{
int value;
int pre; // 記錄其父狀態在隊列中的位置，初始化為⑴；
}；
每次擴大新狀態的時候令新狀態的pre為當前狀態在隊列中的下標，待到達目標狀態以后倒著查回第1個狀態便可獲得解路徑。
深搜：
對深搜，則可另外開1個棧用來記錄當前的合法狀態，每次訪問新狀態前都壓入當前狀態到棧中，回溯時也相應地彈出棧頂，終究這個棧里將逆序記錄解路徑上的節點。大致做法以下：
stack<int> stk;
bool dfs(int loc) {
標記狀態loc已訪問;
stk.push(loc);
for (每一個可能的操作) {
對loc利用操作產生新狀態nstat;
if (nstat合法且未訪問) {
if (dfs(nstat)) return true;
}
}
stk.pop();
撤消loc已訪問標記;
return false;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
