广度优先搜索（BFS）-创新互联

例题： 797. 所有可能的路径

模板题

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名注册、网页空间、营销软件、网站建设、察哈尔右翼中旗网站维护、网站推广。

class Solution
{
public:
    vector>allPathsSourceTarget(vector>& graph)
    {
        vector>ans;
        queue>q;
        vectorv{ 0 };

        q.push(v);

        while (q.empty() == false)
        {
            v = q.front();
            q.pop();
            int node = v.back();

            if (node == graph.size() - 1)
            {
                ans.push_back(v);
            }
            else
            {
                for (auto i : graph[node])
                {
                    vectortemp = v;
                    temp.push_back(i);
                    q.push(temp);
                }
            }
        }

        return ans;
    }
};

102. 二叉树的层序遍历

广度优先搜索在二叉树中的直接应用

class Solution
{
public:
    vector>levelOrder(TreeNode* root)
    {
        vector>ans;       //返回的答案二维数组
        if (root == nullptr)           //防止树为空
        {
            return ans;
        }

        queueq;
        vectorv{ root->val };

        ans.push_back(v);             //手动存入根节点的值，不然会出错
        q.push(root);                 //将根节点进入队列，作为BFS的“源”

        while (q.empty() == false)    //外层的while循环是针对二叉树中的每一层，一次循环便是一层
        {
            vectortemp;
            int size = q.size();

            for (int i = 0; i< size; i++)  //内层的for循环是针对一层中所有节点的遍历
            {
                TreeNode* r = q.front();
                q.pop();

                if (r->left != nullptr)          //先左节点，后右节点，顺序不能错
                {
                    q.push(r->left);
                    temp.push_back(r->left->val);
                }
                if (r->right != nullptr)
                {
                    q.push(r->right);
                    temp.push_back(r->right->val);
                }
            }

            if (temp.empty() == false)     //防止答案中出现空的temp
            {
                ans.push_back(temp);
            }
        }

        return ans;
    }
};

练习： 733. 图像渲染

class Solution
{
public:
    vector>floodFill(vector>& image, int sr, int sc, int color)
    {
        int oldColor = image[sr][sc];
        queue>q;
        pairp(sr, sc);

        if (oldColor == color)
        {
            return image;
        }

        q.push(p);
        image[sr][sc] = color;

        while (q.empty() == false)
        {
            pairtemp;
            p = q.front();
            q.pop();

            if (p.first >0
                && image[p.first - 1][p.second] == oldColor)
            {
                temp.first = p.first - 1;
                temp.second = p.second;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
            if (p.first< image.size() - 1
                && image[p.first + 1][p.second] == oldColor)
            {
                temp.first = p.first + 1;
                temp.second = p.second;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
            if (p.second >0
                && image[p.first][p.second - 1] == oldColor)
            {
                temp.first = p.first;
                temp.second = p.second - 1;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
            if (p.second< image[p.first].size() - 1
                && image[p.first][p.second + 1] == oldColor)
            {
                temp.first = p.first;
                temp.second = p.second + 1;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
        }

        return image;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：广度优先搜索（BFS）-创新互联
当前网址：http://cdxtjz.cn/article/ddihej.html