数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python 中交替颜色最短路径
假设我们有一个有向图，节点标记为 0、1、...、n-1。在这个图中，每条边都用红色或蓝色着色，并且可能存在自环或平行边。red_edges 中的每个 [i, j] 表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每个 [i, j] 表示从节点 i 到节点 j 的蓝色有向边。我们必须找到一个长度为 n 的数组 answer，其中每个 answer[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 不为空时
将三元组 current、color、step 设置为 q[0]，并从 q 中删除
color := 取反 color 的值（true 变为 false，反之亦然）
res[current] := res[current] 和 step 的最小值
如果 color 非零，则
对于 re[current] 中的每个 i
如果对 (i, color) 不在 visited 中，则将 (i, color) 插入 visited 并将 [i, color, step + 1] 插入 q
否则当 color 为 0 时，则
对于 be[current] 中的每个 i
如果对 (i, color) 不在 visited 中，则将 (i, color) 插入 visited 并将 [i, color, step + 1] 插入 q
在主方法中：
res := 一个包含无限大值的数组，其大小为 n
re 和 be := 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 的 i
如果 res[i] = inf，则 res[i] := -1
返回 res
示例（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]
575 次浏览
