admin管理员组

文章数量:1037775

【算法】图论

持续更新中…

1、DFS

单词搜索

代码语言：javascript代码运行次数：0运行复制
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 叉树的层序遍历
代码语言：javascript代码运行次数：0运行复制
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;
    }
};
二叉树的锯齿形层序遍历
  • 二叉树的锯齿形层序遍历

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

代码语言：javascript代码运行次数：0运行复制
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;
    }
};
二叉树最大宽度
  • 二叉树最大宽度
代码语言：javascript代码运行次数：0运行复制

3、多源BFS

腐烂的苹果
  • 腐烂的苹果
代码语言：javascript代码运行次数：0运行复制
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool vis[1001][1001] = {};
    int m, n;
    queue<int> q;
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 && !vis[i][j])
                {
                    vis[i][j] = true;
                    bfs(grid, i, j);
                }
    }
    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        while (!q.empty())
        {
            
        }
        for (int k = 0; k < 4; k++)
        {

        }
    }
};

4、拓扑排序

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-13，如有侵权请联系 cloudcommunity@tencent 删除int遍历队列算法二叉树

【算法】图论

持续更新中…

1、DFS

单词搜索

代码语言：javascript代码运行次数：0运行复制
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 叉树的层序遍历
代码语言：javascript代码运行次数：0运行复制
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;
    }
};
二叉树的锯齿形层序遍历
  • 二叉树的锯齿形层序遍历

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

代码语言：javascript代码运行次数：0运行复制
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;
    }
};
二叉树最大宽度
  • 二叉树最大宽度
代码语言：javascript代码运行次数：0运行复制

3、多源BFS

腐烂的苹果
  • 腐烂的苹果
代码语言：javascript代码运行次数：0运行复制
class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool vis[1001][1001] = {};
    int m, n;
    queue<int> q;
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 && !vis[i][j])
                {
                    vis[i][j] = true;
                    bfs(grid, i, j);
                }
    }
    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        while (!q.empty())
        {
            
        }
        for (int k = 0; k < 4; k++)
        {

        }
    }
};

4、拓扑排序

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-13，如有侵权请联系 cloudcommunity@tencent 删除int遍历队列算法二叉树

本文标签： 算法图论

版权声明：本文标题：【算法】图论 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748297135a2281661.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。