前言

基礎

LeetCode 797. All Paths From Source to Target

• 圖的 Traverse

LeetCode 1743. Restore the Array From Adjacent Pairs

• 使用 HashMap 來記錄不知道大小的圖

LeetCode 207. Course Schedule

• 檢查圖中是否有環

LeetCode 210. Course Schedule II

• Iterate 的順序 ⇒ Post Order 後 Reverse

二分圖

LeetCode 785. Is Graph Bipartite?

LeetCode 886. Possible Bipartition

Union Find

Define Union Find Class

LeetCode 130. Surrounded Regions

LeetCode 990. Satisfiability of Equality Equations

LeetCode 684. Redundant Connection

LeetCode 721. Accounts Merge

• element 型別不為 int 的情況 ⇒ 使用 map 來記錄 element 與 index

Prim + Dijkstra

• Prim: 最小生成樹，dist 為未標記集合與已標記集合的距離。

• Dijkstra: 最短路徑，dist 為未標記集合與起點的距離。

• Time Complexity:

• Space Complexity:

LeetCode 1135. Connecting Cities With Minimum Cost

LeetCode 1584. Min Cost to Connect All Points

• 使用 Priority Queue(Min Heap) 來取代 Prim Class

LeetCode 743. Network Delay Time

• 可以使用 greater 來生成最小堆，不必自行定義 Functor

LeetCode 1631. Path With Minimum Effort

• 圖中需要記錄三個元素 ⇒ Tuple

LeetCode 1091. Shortest Path in Binary Matrix

LeetCode 1514. Path with Maximum Probability

LeetCode 3286. Find a Safe Walk Through a Grid

LeetCode 1976. Number of Ways to Arrive at Destination

• Graph 與 dp 的結合

Floyd Warshall

• 建出初始距離表

• 將結點本身到結點本身的距離設為 0

• 以 節點 走到 節點 ，以 節點 作為中間點，則

• 針對每個節點跑一次，總共 的時間複雜度，即可建出圖中任意節點走到任意節點的最短距離表

LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

LeetCode 2976. Minimum Cost to Convert String I

LeetCode

LeetCode

LeetCode

LeetCode