資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
