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

閱讀時間約 7 分鐘
raw-image

這題的題目在這裡:

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


測試範例:

Example 1:

raw-image
Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

raw-image
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



85會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
Coin Change + DP 策略_Leetcode 面試題 上機考 題目 詳細解說
Coin Change + DP 策略_Leetcode 面試題 上機考 題目 詳細解說
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
Dealing range 可以輔助找到你的交易區間。找到兩個高低點各自都有Liquidity grab,那麼這高低點之間就是所謂的Dealing Range。交易區間的用意在於可以知道Premium and Discount 的概念,以及找正確的高低點。
Thumbnail
題目敘述 題目會給我們一個4位數字的數字鎖,還有解鎖的密碼target,和陷阱數字deadends(假如遇到的會鎖會直接卡住,不能在撥動轉盤了)。 預設開始的狀態是0000,請問,最少要撥動轉盤幾次才能解鎖? 題目的原文敘述 測試範例 Example 1: Input: deaden
Thumbnail
題目敘述 圖目會給定我們一串已知變數作除法的值,以分子在前,分母在後的形式表達。 要求我們針對未知的變數除法作計算,以浮點數的形式返回答案;如果無解,返回-1.0。 題目的原文敘述 測試範例 Example 1: Input: equations = [["a","b"],["b",
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
Thumbnail
這篇文章想要聊一下,在使用ControlNet的reference_only時,因為原始參考圖實在太過於模糊,造成生產出來的圖片品質不佳的情況下要怎麼使用一些技巧提高參考圖的精細度。
Thumbnail
這篇文章要來分享的是,怎麼把一張糊掉的圖精細化。 這個問題最主要的對象是已經有明顯的提示詞,並且以ControlNet的refernece_only來生產的圖。
Thumbnail
在上一篇文章中,我使用人偶圖產出了一個姿勢正確,但是手指錯亂且臉型崩潰的半成品圖,這一篇我要繼續修正這些問題,得到一個草稿圖,再使用這個草稿製作大張的完成圖。
Thumbnail
前言 本篇要介紹一個流程,讓我們可以使用人偶姿勢生成網站或App來製作特意的姿勢與角度,並且經過一套流程之後,轉化成我們要的人物。 在使用Stable Diffusion生成圖片時,最常遇見的問題是人物的動作或位置不照我們的心意生成,尤其是一些高動態或不常見的姿勢與角度,或者手持物品,在某些模型上是
Thumbnail
本篇要來討論一個很有趣的組合技巧,就是用有範圍的隨機提示詞來生成許多角色設定圖。
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
Dealing range 可以輔助找到你的交易區間。找到兩個高低點各自都有Liquidity grab,那麼這高低點之間就是所謂的Dealing Range。交易區間的用意在於可以知道Premium and Discount 的概念,以及找正確的高低點。
Thumbnail
題目敘述 題目會給我們一個4位數字的數字鎖,還有解鎖的密碼target,和陷阱數字deadends(假如遇到的會鎖會直接卡住,不能在撥動轉盤了)。 預設開始的狀態是0000,請問,最少要撥動轉盤幾次才能解鎖? 題目的原文敘述 測試範例 Example 1: Input: deaden
Thumbnail
題目敘述 圖目會給定我們一串已知變數作除法的值,以分子在前,分母在後的形式表達。 要求我們針對未知的變數除法作計算,以浮點數的形式返回答案;如果無解,返回-1.0。 題目的原文敘述 測試範例 Example 1: Input: equations = [["a","b"],["b",
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
Thumbnail
這篇文章想要聊一下,在使用ControlNet的reference_only時,因為原始參考圖實在太過於模糊,造成生產出來的圖片品質不佳的情況下要怎麼使用一些技巧提高參考圖的精細度。
Thumbnail
這篇文章要來分享的是,怎麼把一張糊掉的圖精細化。 這個問題最主要的對象是已經有明顯的提示詞,並且以ControlNet的refernece_only來生產的圖。
Thumbnail
在上一篇文章中,我使用人偶圖產出了一個姿勢正確,但是手指錯亂且臉型崩潰的半成品圖,這一篇我要繼續修正這些問題,得到一個草稿圖,再使用這個草稿製作大張的完成圖。
Thumbnail
前言 本篇要介紹一個流程,讓我們可以使用人偶姿勢生成網站或App來製作特意的姿勢與角度,並且經過一套流程之後,轉化成我們要的人物。 在使用Stable Diffusion生成圖片時,最常遇見的問題是人物的動作或位置不照我們的心意生成,尤其是一些高動態或不常見的姿勢與角度,或者手持物品,在某些模型上是
Thumbnail
本篇要來討論一個很有趣的組合技巧,就是用有範圍的隨機提示詞來生成許多角色設定圖。