進階圖論題目: Leetcode #847 Shortest Path Visiting All Nodes

這題的題目在這裡:

題目會給定我們一張圖和對應的相鄰矩陣，要求我們返回一筆畫拜訪所有節點的最短路徑長，起終點不拘。

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.
• If graph[a] contains b, then graph[b] contains a.
• The input graph is always connected.

演算法:

回顧一些圖論的基本演算法，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