這題的題目在這裡:
題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
測試範例:
Example 1:
Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
約束條件:
Constraints:
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i]
does not contain i
.graph[a]
contains b
, then graph[b]
contains a
.演算法:
回顧一些圖論的基本演算法,BFS, DFS, MST最小生成樹, Shortest Path給定起點的最短路徑…等。哪個比較適合呢?
BFS最適合? 為什麼,因為BFS先天具有點波源擴散的特質,由起點往外擴散,逐層探索,當滿足終止條件時(以本題目為例,就是拜訪過所有節點),擴散層數 = 最短路徑。
這題的困難點又在哪呢? 因為起終點不固定,但是又要求必須拜訪所有節點。
所以,一開始初始化的時候,必須把所有節點都納入Source 起始點。
(因為事先不知道從哪個節點走,可以產生最短的一筆畫路徑,所有的節點都必須納入考量。)
traversal_queue = deque( [(node_idx, 1 << node_idx , 0) for node_idx in range(n) ] )
接著,必須防止進入迴圈死循環,因為題目輸入的圖Grpah,可能帶有環路(Cycle)。
所以,在設計visited set和推入traversal queue時,必須同步考慮到當下的搜索狀態search state。當BFS 進行中,必須檢查(node index, search state)沒有重複,才走下一步。
visited = { (node_idx, 1 << node_idx ) for node_idx in range(n) }
最後,就是設定終止條件,題目已經給定是一筆畫路徑,而且必須拜訪所有節點。所以,如果當下search state的bit mask已經拜訪過所有節點,則BFS演算法抵達終止條件,當下的搜索步長 = 擴散層數 = 一筆畫拜訪所有節點的最短路徑長。
# We've visited all nodes in graph G at least once
if cur_state == all_node_visited:
return path_length
程式碼:
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
# n = total node count = height of adjacency matrix
n = len(graph)
# Initialize traversal queue
# parameter of tuple: (node idx, state mask, visiting path length)
traversal_queue = deque( [(node_idx, 1 << node_idx , 0) for node_idx in range(n) ] )
# parameter of visited tuple: (node index, search state mask)
visited = { (node_idx, 1 << node_idx ) for node_idx in range(n) }
# Mask of all node visited
all_node_visited = (1 << n) - 1
# Launch BFS traversal from each node in graph G as source
while traversal_queue:
cur_node, cur_state, path_length = traversal_queue.popleft()
# We've visited all nodes in graph G at least once
if cur_state == all_node_visited:
return path_length
# Visit neighbor of current node
for neighbor_idx in graph[cur_node]:
next_state = cur_state | (1 << neighbor_idx)
next_length = path_length + 1
# If pair (neighbor index, next state) is not seen before
if (neighbor_idx, next_state) not in visited:
traversal_queue.append( (neighbor_idx, next_state, next_length) )
visited.add( (neighbor_idx, next_state) )
return -1
令n = 輸入圖中的總節點數
時間複雜度:
O( n² * 2^n )
BFS 圖論演算法基本複雜度為O( V + E ) = O( n + n² ),
當稠密圖時,Edge最多可以有C(n,2)條邊 = O( n² )
此外,在BFS探索的每一步中,需要額外紀錄O(2^n) seach state mask搜索狀態的遮罩。
因為總共有n個節點,每個節點有兩種可能(拜訪過 或 沒拜訪過),遮罩最多有O(2^n)種不同狀態。
空間複雜度:
O( n * 2^n )
耗費在Traversal queue 和 visited set上,最多有n個節點,拜訪每個節點當下伴隨最多2^n種狀態。
Reference:
[1] Python O( (n²) * (2^n) ) by BFS + bitmask — Shortest Path Visiting All Nodes — LeetCode