Python中具有交替颜色的最短路径
假设我们有向图，其节点标记为0、1，...，n-1。在此图中，每个边缘都用红色或蓝色上色，并且可能有自边缘或平行边缘。red_edges中的每个[i，j]表示从节点i到节点j的红色有向边。类似地，blue_edges中的每个[i，j]表示从节点i到节点j的蓝色有向边。我们必须找到长度为n的数组答案，其中每个答案[X]是从节点0到节点X的最短路径的长度，以使边缘颜色沿路径交替（如果不这样，则为-1）存在）。
因此，如果输入像n=3，red_edges=[[0,1]，[1,2]]和blue_edges=[]，那么输出将是[0，1，-1]
为了解决这个问题，我们将遵循以下步骤-
定义一个名为bfs()的方法，它将使用re，be，f和n
定义一个称为Visited的集合，定义一个队列并插入一个三元组[0，f，0]
当q不为空时
对于每一个我来说[当前]
如果未访问对(i,color)，则将(i,color)插入Visited并将[i，color，step+1]插入q
对于每个我[当前]
如果未访问对(i,color)，则将(i,color)插入Visited并将[i，color，step+1]插入q
将三线态电流，颜色，步长设置为q[0]，然后从q中删除
color：=补全color的值（真为假，反之亦然）
res[current]：=res[current]和step的最小值
如果颜色不为零，则
否则当color为0时
在主要方法中-
res：=一个无穷大值的数组，其大小为n
reand是：=n个空数组的数组
对于r中的每个元素i：将i[1]插入re[i[0]]
对于b中的每个元素i：将i[1]插入be[i[0]]
调用bfs(re,be,false,n)并调用bfs(re,be,true,n)
当我的范围是0到res的长度–1
如果res[i]=inf，则res[i]：=-1
返回资源
示例(Python)
让我们看下面的实现以更好地理解-
class Solution(object):
def shortestAlternatingPaths(self, n, r, b):
self.res = [float("inf")] * n
re = [[] for i in range(n) ]
be = [[] for i in range(n) ]
for i in r:
re[i[0]].append(i[1])
for i in b:
be[i[0]].append(i[1])
self.bfs(re,be,False,n)
self.bfs(re,be,True,n)
for i in range(len(self.res)):
if self.res[i] == float('inf'):
self.res[i]=-1
return self.res
def bfs(self,re,be,f,n):
visited = set()
queue = [[0,f,0]]
while queue:
current,color,step = queue[0]
queue.pop(0)
color = not color
self.res[current] = min(self.res[current],step)
if color:
for i in re[current]:
if (i,color) not in visited:
visited.add((i,color))
queue.append([i,color,step+1])
elif not color:
for i in be[current]:
if (i,color) not in visited:
visited.add((i,color))
queue.append([i,color,step+1])
ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1], [1,2]], []))输入值
3 [[0,1],[1,2]] []
输出结果
[0,1,-1]