为什么此BFS解决方案无法通过此测试用例？

Question

以下是我对leetcode问题的解决方案https://leetcode.com/problems/shortest-path-with-alternating-colors/。我执行了BFS两次，因为初始状态为0的2种情况。它可能来自红色或蓝色节点。然后执行常规BFS，每次迭代后切换状态因为必须切换颜色。

失败的测试用例：-5[[0,1]，[1,2]，[2,3]，[3,4]][[1,2]，[2,3]，[3,1]]

我的BFS显然没有到达节点'4'。

class Solution {
public:

    void bfs(int state,vector<int>& dist,unordered_map<int,vector<int>>& red,unordered_map<int,vector<int>>& blue,vector<int> stat)
    {
        int dep=1;
        queue<int> q;
        q.push(0);
        while(q.size()!=0)
        {
            if(state==-1)
            {
            int si=q.size();
            for(int i=0;i<si;i++)
            {
            int a=q.front();
            q.pop();
            for(auto& x:red[a])
            {
                if(stat[x]==10)
                    continue;
                if(dist[x]==-1||(stat[x]==state))
                {
                q.push(x);
                if(dist[x]==-1)
                {
                    dist[x]=dep;
                    stat[x]==-1*state;
                }
                else
                {
                    dist[x]=min(dist[x],dep);
                    stat[x]=10;
                }
                }
            }}
                state=1;}

            else
            {

            int si=q.size();
            for(int i=0;i<si;i++)
            {
                int a=q.front();
                q.pop();
                for(auto& x:blue[a])
                {
                if(stat[x]==10)
                    continue;
                if(dist[x]==-1||(stat[x]==state))
                {
                q.push(x);
                if(dist[x]==-1)
                {
                    dist[x]=dep;
                    stat[x]==-1*state;
                }
                else
                {
                    dist[x]=min(dist[x],dep);
                    stat[x]=10;
                }
                }
                }
            }
            state=-1;
            }
            dep++;
        }
    }
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges)     {
        unordered_map<int,vector<int>> red,blue;
        vector<int> dist(n,-1);
        vector<int> dis(n,-1);
        for(auto& x:red_edges)
        {
            red[x[0]].push_back(x[1]);
        }
        for(auto& x:blue_edges)
        {
            blue[x[0]].push_back(x[1]);
        }
        dist[0]=0;
        dis[0]=0;
        int dep=1;
        vector<int> stat(n,0);
        stat[0]=-1;
        bfs(-1,dist,red,blue,stat);
        stat[0]=1;
        bfs(1,dis,red,blue,stat);
        for(int i=0;i<n;i++)
        {
            if(dis[i]==-1)
                continue;
            if(dist[i]==-1)
                continue;
            dist[i]=min(dist[i],dis[i]);
        }
        return dist;
    }
};

Answer 1

您不能只使用BFS，因为可以从任何顶点中取出的边缘取决于您到达那里的方式-到达哪种类型的边缘。

解决此类问题的常用方法通常称为“图形分层”。您（从概念上来说）制作图形的2副本，[[G 0和_{G 1 [>]}，然后使所有蓝色边缘从G 0到_G 1，并使所有蓝色边缘从_G 1到_G 0] >。_{现在，此新的2层图形中的}

每个

路径对应于原始图形中的交替颜色路径，反之亦然。

您可以仅在此新图上使用BFS来查找所需的路径。

[当您习惯了这一点后，您可以用一种更简单的方式来考虑它：您只使用BFS，但不是在队列中使用像[reached

v

]之类的状态，而是使用像[reached v，通过蓝色]。通常，当我们在现实生活中使用图算法时，没有给出任何实际图，而是对隐式图进行操作：https://en.wikipedia.org/wiki/Implicit_graph