【算法】DFS、BFS、拓扑排序

⭐️个人主页：@小羊 ⭐️所属专栏：算法很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

持续更新中…

1、DFS

单词搜索

class Solution 
{int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};bool check[101][101] = {};// 标记数组，防止上下左右找的时候重复遍历int m, n;
public:bool exist(vector<string>& board, string word){m = board.size(), n = board[0].size();for (int i = 0; i < m; i++)for (int j = 0; j <n; j++)if (board[i][j] == word[0]){check[i][j] = true;// 找到第一个字符了，开始找下一个字符if (dfs(board, word, i, j, 1)) return true;check[i][j] = false;}return false;}bool dfs(vector<string>& board, string& word, int i, int j, int pos){// 找到单词结尾就返回if (pos == word.size()) return true;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && board[x][y] == word[pos]){check[x][y] = true;if (dfs(board, word, x, y, pos + 1)) return true;check[x][y] = false;}}// 如果走到这里说明没有进递归，也就是四个方位都没找到字符return false;}
};

2、BFS

通常利用队列first in first out的特点，统计出每层的q.size()以遍历每一层。

N 叉树的层序遍历

N 叉树的层序遍历

在这里插入图片描述

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret;if (root == nullptr) return ret;queue<Node*> q;q.push(root);while (!q.empty()){vector<int> tmp;int size = q.size();while (size--){tmp.push_back(q.front()->val);for (auto e : q.front()->children){q.push(e);}q.pop(); // 利用父节点把子节点全部插入队列后再删除父节点}ret.push_back(tmp);}return ret;}
};

二叉树的锯齿形层序遍历

二叉树的锯齿形层序遍历

在这里插入图片描述

遇到二叉树的题一定注意判断有没有左右子节点，不然很容易对空节点解引用。

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;if (root == nullptr) return ret;queue<TreeNode*> q;q.push(root);int flag = 1;while (!q.empty()){int size = q.size();vector<int> tmp;while (size--){auto t = q.front();tmp.push_back(t->val);if (t->left) q.push(t->left);if (t->right) q.push(t->right);q.pop();}flag *= -1;if (flag > 0) reverse(tmp.begin(), tmp.end());ret.push_back(tmp);}return ret;}
};

二叉树最大宽度

二叉树最大宽度

3、多源BFS

腐烂的苹果

腐烂的苹果

在这里插入图片描述

class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};queue<pair<int, int>> q;int m, n, ret = 0;bool vis[1001][1001] = {};
public:int rotApple(vector<vector<int> >& grid) {m = grid.size(), n = grid[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if(grid[i][j] == 2) q.push({i, j});while (!q.empty()){int sz = q.size();ret++;while (sz--){auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1){vis[x][y] = true;q.push({x, y});}}}}for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == 1 && !vis[i][j]) return -1;return ret - 1;}
};