BFS题：颜色交替的最短路径

爱被打了一巴掌 2023-10-06 10:07 38阅读 0赞

## BFS题：颜色交替的最短路径 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

#### 思路： ####

颜色交替的解决办法：  
我们每次传递时，将上一次遍历的边的颜色信息带上，在下一次遍历时，选择不同的颜色的邻接节点,节点信息在队列中的存储为（node,color)，即既存储节点的编号，又存储上一次遍历边的颜色信息

由于存在环和平行边，使用数组visit\[x\]\[y\]\[color\] = 1,代表从节点x到节点y的且颜色为color的边被访问过，防止重复访问。

对红色和蓝色边分别使用map建立邻接表，初始放入队列的信息为（0,1）和（0，0）,分别表示从起点开始，下一次边颜色为蓝和为红（上一条边颜色为红和为蓝两种情况）

在BFS函数中需判断队列头保存的上一条边的颜色，若为红，在蓝色边邻接表中进行遍历，向队列中放入新元素时，颜色信息改变为蓝色。  
上一条边的信息为蓝色时处理过程类似，即在红色边邻接表中进行遍历

#### 代码： ####

class Solution {
        
    public:
        vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        
            unordered_map<int,vector<int>> red;
            unordered_map<int,vector<int>> blue;
            int visited[100][100][2];
            int step=0;
            int i;
            vector<int> ans( n,1e+06 );
            queue< pair<int,int> > q;
            for( auto temp:red_edges )
                red[ temp[0] ].push_back( temp[1] );
            for( auto temp:blue_edges )
                blue[ temp[0] ].push_back( temp[1] );
            memset( visited,0,sizeof(visited) );
            q.push( make_pair( 0,1 ) );
            q.push( make_pair( 0,0 ) );
            while( !q.empty() )
            {
           
                step++;
                int size=q.size();
                for( i=0;i<size;i++ )
                {
        
                    int cur=q.front().first;
                    int color=q.front().second;
                    q.pop();
                    if( color==1 )
                    {
        
                        for( auto temp:blue[cur] )
                        {
        
                            if( visited[cur][temp][0]==0 )
                            {
        
                                ans[temp]=min( ans[temp],step );
                                visited[cur][temp][0]=1;
                                q.push( make_pair(temp,0) );
                            }
                        }
                    }
                    else
                    {
        
                        for( auto temp:red[cur] )
                        {
        
                            if( visited[cur][temp][1]==0 )
                            {
        
                                ans[temp]=min( ans[temp],step );
                                visited[cur][temp][1]=1;
                                q.push( make_pair(temp,1) );
                            }
                        }
                    }
                }
            }
            ans[0]=0;
            for( i=1;i<n;i++ )
                if( ans[i]>=1e+05 )
                    ans[i]=-1;
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531153757568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200531153809814.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70