10.Algorithms: Searching + BFS + DFS 學習筆記

學習資料來源: Master the Coding Interview: Data Structures + Algorithms

此單元會談到的數個Search類型：Linear Search, Binary Search, Depth First Search, Breadth First Search

【Linear Search】

一個一個搜尋陣列中的元件，直到找到目標或搜尋完整個陣列

【Binary Search】

元素為數字且經過排序，從一半開始搜尋

【 Breadth First Search】 O(n)

• 每層由左到右，直到找到目標或搜尋完整個tree
• 會使用到額外的記憶體，因為需要追蹤子node
• 目標在較上層時適用

優點: 尋找最短路徑、搜尋時會越來越接近目標

缺點: 需要較多記憶體

【Depth First Search】 O(n)

• 左邊每個階層找完再找右邊(每邊子層找完後回到上層)，直到找到目標或搜尋完整個tree
• 需要較少的記憶體，不用儲存每個子元件的指向
• 目標在較低層時適用

優點: 需要較少記憶體、確認目標是否存在

缺點: 需要找到底層因此可能會搜尋較慢

練習: 適合哪一種搜尋方法？(BFS vs DFS)

• If you know a solution is not far from the root of the tree: BFS
• If the tree is very deep and solutions are rare: BFS (DFS 需要花較多時間)
• If the tree is very wide: DFS (BFS 需要較多記憶體)
• If solutions are frequent but located deep in the tree: DFS
• Determining whether a path exists between two nodes: DFS
• Finding the shortest path: BFS

【用JS實作 BFS】

沿用先前的BinarySearchTree完成BFS

【用JS實作 DFS】

沿用先前的BinarySearchTree完成DFS

三種實作類型：

1.InOrder 小至大排序－[1, 4, 6, 9, 15, 20, 86]

2.PreOrder 重現tree順序－[9, 4, 1, 6, 20, 15, 86]

3.PostOrder 由左底層向上，換右底層向上，最後root值－[1,6,4,15,86,20,9]

【其他：Dijkstra & Bellman-Ford Algorithms】

• 考量edge的最短路徑(edge為兩個node之間的連結)
• Bellman-Ford algorithm 比 Dijkstra Algorithms 更有效處理最短路徑問題，因為允許處理負值
• Dijkstra Algorithms 執行速度較Bellmon Ford algorithms快

回到筆記列表，文章中的內容如果有誤，歡迎提醒告知，謝謝!