@TOC
前言
本文我們主要來介紹dfs和bfs的基礎知識在加以幾個必要的習題說明，搜索算法
dfs和bfs
dfs
深度優先搜索算法（簡稱DFS）
：一種用于遍歷或搜索樹或圖的算法。 沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過或者在搜尋時結點不滿足條件，搜索將回溯到發現節點v的那條邊的起始節點。整個進程反復進行直到所有節點都被訪問為止。屬于盲目搜索,最糟糕的情況算法時間復雜度為O(!n)。
是遞歸回溯的方法來進行搜索，dfs：
一條路走到黑的方式來進行搜索，我們來看下面這張圖
從每個節點一條路走下去，直到走不通為止
dfs全排列問題
以三為例，dfs的搜索順序如下圖所示
#include using namespace std; const int N = 10; int path[N];//保存序列 int state[N];//數字是否被用過 int n; void dfs(int u) { if(u > n)//數字填完了，輸出 { for(int i = 1; i <= n; i++)//輸出方案 cout << path[i] << " "; cout << endl; } for(int i = 1; i <= n; i++)//空位上可以選擇的數字為:1 ~ n { if(!state[i])//如果數字 i 沒有被用過 { path[u] = i;//放入空位 state[i] = 1;//數字被用，修改狀態 dfs(u + 1);//填下一個位 state[i] = 0;//回溯，取出 i } } } int main() { cin >> n; dfs(1); }
dfs N皇后問題
n皇后
「N 皇后問題」研究的是如何將 N 個皇后放置在 N×N 的棋盤上，并且使皇后彼此之間不能相互攻擊。
皇后的走法是：可以橫直斜走，格數不限。因此要求皇后彼此之間不能相互攻擊，等價于要求任何兩個皇后都不能在同一行、同一列以及同一條斜線上。
直觀的做法是暴力枚舉將 N個皇后放置在 N×N 的棋盤上的所有可能的情況，并對每一種情況判斷是否滿足皇后彼此之間不相互攻擊。
對應今天的主題，我們就先用dfs深搜的方式來寫這個n皇后問題
思路：
顯然，每個皇后必須位于不同行和不同列，因此將 N 個皇后放置在 N ×N 的棋盤上，一定是每一行有且僅有一個皇后，每一列有且僅有一個皇后，且任何兩個皇后都不能在同一條斜線上。
具體做法：
使用一個數組記錄每行放置的皇后的列下標，依次在每一行放置一個皇后。每次新放置的皇后都不能和已經放置的皇后之間有攻擊：即新放置的皇后不能和任何一個已經放置的皇后在同一列以及同一條斜線上，并更新數組中的當前行的皇后列下標。當 N 個皇后都放置完畢，則找到一個可能的解。當找到一個可能的解之后，將數組轉換成表示棋盤狀態的列表，并將該棋盤狀態的列表加入返回列表。
#include using namespace std; const int N = 20; // bool數組用來判斷搜索的下一個位置是否可行 // col列，dg對角線，udg反對角線 // g[N][N]用來存路徑 int n; char g[N][N]; bool col[N], dg[N], udg[N]; void dfs(int u) { //搜到 if (u == n) { for (int i = 0; i < n; i ++ ) puts(g[i]); puts(""); return; } //對n個位置按行搜索 for (int i = 0; i < n; i ++ ) // 剪枝(對于不滿足要求的點，不再繼續往下搜索) // udg[n - u + i]，+n是為了保證下標非負 if (!col[i] && !dg[u + i] && !udg[n - u + i]) { g[u][i] = 'Q'; col[i] = dg[u + i] = udg[n - u + i] = true; dfs(u + 1); col[i] = dg[u + i] = udg[n - u + i] = false; // 恢復現場 g[u][i] = '.'; } } int main() { cin >> n; for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) g[i][j] = '.'; dfs(0); return 0; }
最長快樂字符串
int used; char GetNext(int *a, int *b, int *c) { int m = *a, n = *b, p = *c; if (used == 1) { /* 哪個用過了，不參與比較 */ m = 0; } if (used == 2) { n = 0; } if (used == 3) { p = 0; } if ((m >= n) && (m >= p) && (m > 0)) { (*a)--; used = 0; return 'a'; } if ((n >= m) && (n >= p) && (n > 0)) { (*b)--; used = 0; return 'b'; } if ((p >= m) && (p >= n) && (p > 0)) { (*c)--; used = 0; return 'c'; } return '0'; } char * longestDiverseString(int a, int b, int c) { used = 0; char *res = calloc(a + b + c + 1, sizeof(char)); char t; int cnt = 0; while (true) { t = GetNext(&a, &b, &c); if (t != '0') { res[cnt++] = t; } else { break; } if ((cnt >= 2) && (res[cnt - 2] == 'a') && (res[cnt - 1] == 'a')) { used = 1; } if ((cnt >= 2) && (res[cnt - 2] == 'b') && (res[cnt - 1] == 'b')) { used = 2; } if ((cnt >= 2) && (res[cnt - 2] == 'c') && (res[cnt - 1] == 'c')) { used = 3; } } return res; }
二叉樹的最近祖先
dfs二叉樹的最近祖先
值得注意：一個節點也可以是它自己的祖先，二叉搜索樹，對于根節點來說，左邊比根小，右邊比根大，可以做截枝
暴搜
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //if (root == p || root == q) return root; if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q); if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q); return root; } };
class Solution { public: vector getPath(TreeNode* root, TreeNode* target) { vector path; TreeNode* node = root; while (node != target) { path.push_back(node); if (target->val < node->val) { node = node->left; } else { node = node->right; } } path.push_back(node); return path; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector path_p = getPath(root, p); vector path_q = getPath(root, q); TreeNode* ancestor; for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) { if (path_p[i] == path_q[i]) { ancestor = path_p[i]; } else { break; } } return ancestor; } };
bfs
廣度優先搜索，像下面這張圖一樣，一層一層去搜索，我們也不難看出，當邊的權值都是一樣的時候，第一次搜索就是最短路，后面的搜索都比第一次大，引出最短路問題，這個我們后面再說。
迷宮
dfs保證搜到終點，但是不能保證搜到的是最短的
#include//萬能頭文件 using namespace std; const int MAXSIZE_N=1000; const int MAXSIZE_M=100000; struct state{ int x; int y; };//養成好習慣~結構體有利于我們調整程序 bool IsUsed[MAXSIZE_N][MAXSIZE_N];//記錄迷宮bfs的遍歷狀態 bool maze[MAXSIZE_N][MAXSIZE_N];//maze用于記錄迷宮本身 int lookUpTable[MAXSIZE_N][MAXSIZE_N]={0};//建立查詢表，記憶化搜索 int n,m; int cnt=0;//記錄可走的格子數 state dir[4]={{1,0},{-1,0},{0,1},{0,-1}}; void InitAll() { // memcpy(maze,neverMaze,sizeof(neverMaze)); // memcpy(IsUsed,neverUsed,sizeof(neverUsed));//速度過慢 cnt=0; } bool IsSafe(state now,state next) { return(next.x>=0&&next.x=0&&next.y1或1->0 &&(IsUsed[next.x][next.y]!=true);//沒有染過色or沒走過 } void bfs(state start) { queue Q; queue memoryPos;//用于記憶化搜索，記錄走過的點，提高速度 IsUsed[start.x][start.y]=true; cnt++; Q.push(start); memoryPos.push(start); while(!Q.empty()){ state now=Q.front(); Q.pop(); for(int i=0;i<4;i++){ state next=now; next.x+=dir[i].x; next.y+=dir[i].y; if(IsSafe(now,next)){ IsUsed[next.x][next.y]=true; memoryPos.push(next); cnt++; Q.push(next); } } } while(!memoryPos.empty()) { state next=memoryPos.front(); //把走過的點都記到表中 memoryPos.pop(); lookUpTable[next.x][next.y]=cnt; } } int main() { std::ios::sync_with_stdio(false);//加快輸入流的速度 cin>>n>>m; string in[n]; state start[m]; for(int i=0;i>in[i]; for(int i=0;i>start[i].x>>start[i].y; start[i].x-=1;//調整輸入的坐標到從零開始的坐標 start[i].y-=1; } for(int i=0;i
數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
