平安歸途 最安全的一條路 (圖論應用) Leetcode #2812本篇文章討論了在給定二元矩陣中,如何使用Dijkstra算法找出從左上角到右下角的最安全路徑的安全分數。包括定義曼哈頓距離、最安全路徑的算法以及時間複雜度和空間複雜度分析。最終推薦Dijkstra algorithm和priority queue的使用。文章提供了參考文獻LeetCode的連結。 一魚多吃: 從不同方法確認 兩點之間的路徑存在與否今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目,來回顧以前學過的DFS、BFS和Disjoint Set,鞏固圖論演算法的知識點。
英文的題目敘述在這裡
題目敘述
給定我們已知n個節點的圖,和圖上的每一條無向邊edges。
請問給定的起點start和終點end是否存在一條路徑可 一魚多吃: 從 島嶼周長 理解 圖論演算法的本質今天的官方每日一題是Island Perimeter島嶼周長,很有趣的一題。
題目非常直觀好懂。也很適合拿來作為多角度複習、回顧圖論演算法的好題目。
英文的題目敘述在這裡
題目敘述
題目會給我們一個二維陣列當作地圖,格子點為1代表陸地,格子點為0代表海洋。
要求我們以四連通N4的方式拜訪 合縱連橫: 從 圖論的應用題 理解BFS背後的本質這篇文章,會帶著大家複習以前學過的BFS框架,
並且以圖論的應用題與概念為核心,
貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。
BFS 框架 + 演算法 虛擬碼
# Queue 通常初始化成根結點,作為起點
BFS_queue = deque([root])
# 先