廣度優先
含有「廣度優先」共 36 篇內容
全部內容
發佈日期由新至舊
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。
我們專注於廣度優先搜尋(BFS)演算法，以等權圖的最短路徑為例，
詳細說明如何利用BFS從起點擴散到終點，並且提供詳細的程式碼範例。
透過實作，讀者能夠更清楚理解圖論及BFS的應用，並體會水波紋擴散模型的重要性。
題目敘述 386. Lexicographical Numbers
給定一個數字n，請實作一個字典序(Lexical order)排列的報數機，
依字典序輸出所有1~n的數字。
你必須實現一個O(n) time線性時間，O(1) extra space常數額外空間的演算法。
🫣
定義
圖Graph: 由節點和邊所組成的一個網狀資料結構。
圖的表達方式Graph representation:
常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。
本文以adjacenct list作為示範。
節點Vertex: 節點
二元搜尋樹（Binary Search Tree，簡稱 BST）是一種特殊的二元樹結構，
具有以下特性：
左子樹：左子樹上所有節點的值均小於該節點的值。
右子樹：右子樹上所有節點的值均大於該節點的值。
無重複值：每個節點的值都是唯一的。
這些特性使得二元搜尋樹在搜尋、插入和刪除操作具有較佳的效能。
接著來進入圖論的重點之一，Tree與Binary Tree。
二元樹（Binary Tree）是一種樹狀數據結構，其中每個節點最多有兩個子節點，通常稱為左子節點和右子節點。這些子節點可以是其他節點或空節點（即無子節點）。
二元樹是其他進階樹的基礎，可延伸推廣到Binary Search Tree
看樣子真的要找時間來學
本篇文章討論了在給定二元矩陣中，如何使用Dijkstra算法找出從左上角到右下角的最安全路徑的安全分數。包括定義曼哈頓距離、最安全路徑的算法以及時間複雜度和空間複雜度分析。最終推薦Dijkstra algorithm和priority queue的使用。文章提供了參考文獻LeetCode的連結。
今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目，來回顧以前學過的DFS、BFS和Disjoint Set，鞏固圖論演算法的知識點。
英文的題目敘述在這裡
題目敘述
給定我們已知n個節點的圖，和圖上的每一條無向邊edges。
請問給定的起點start和終點end是否存在一條路徑可
今天的官方每日一題是Island Perimeter島嶼周長，很有趣的一題。
題目非常直觀好懂。也很適合拿來作為多角度複習、回顧圖論演算法的好題目。
英文的題目敘述在這裡
題目敘述
題目會給我們一個二維陣列當作地圖，格子點為1代表陸地，格子點為0代表海洋。
要求我們以四連通N4的方式拜訪
付費限定
這篇文章，會帶著大家複習以前學過的BFS框架，
並且以圖論的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
BFS 框架 + 演算法 虛擬碼
# Queue 通常初始化成根結點，作為起點
BFS_queue = deque([root])
# 先
付費限定
題目敘述
題目會給定我們一顆二元樹的根結點，要求我們計算這棵樹的好結點Good node有多少個?
好結點Good node的定義:
某個節點v是好結點，假如從Root node根結點 到 結點v沿途的節點值都小於等於節點v的節點值。
如果還是覺得很模糊，看下方的測試範例就可以很清楚了解
