Circular Queue
graph LR
A[A] --> B[B]
B --> C[C]
C --> D[D]
D --> A[A]一般的隊列(Queue)
| Queue | Circular Queue | |
|---|---|---|
| 資料排列方式 | 線性順序排列 | 循環順序排列,即將尾端和前端連接起來 |
| 插入和刪除操作 | 刪除操作都在前端進行 插入操作都在尾端進行 |
同樣是前端刪除、尾端插入(FIFO) 索引到底會繞回開頭 |
| 空間利用率(陣列實作) | 低:出列後前端空出的位置無法再用 | 高:前端空出的位置可重複利用 |
| 插入、刪除效率 | O(1) | O(1) |
深度優先搜尋 (Depth-First Search, DFS)
深度優先搜尋 (DFS) 是一種用於搜尋圖或樹結構中所有頂點的遞迴演算法。
它會沿著一條路徑一直深入到不能再走為止,然後回溯並探索其他路徑。
例如,假設我們有一個圖 G,其節點為 {0, 1, 2, 3},邊為 {(0, 1), (0, 2), (1, 2), (2, 3)}。
如果從節點 2 開始步驟如下:
- 訪問節點 2
我們首先訪問節點 2,並將其標記為已訪問。 - 選擇並訪問一個相鄰的未訪問節點
從節點 2 的相鄰節點中選擇一個未訪問的節點(假設選擇節點 3),並訪問它。標記節點 3 為已訪問。 - 繼續深入訪問節點 3 的相鄰未訪問節點
檢查節點 3 的相鄰節點,發現節點 3 沒有未訪問的相鄰節點,則回溯到節點 2。 - 回溯並選擇另一個相鄰的未訪問節點
回到節點 2,選擇另一個相鄰的未訪問節點(節點 0),並訪問它。標記節點 0 為已訪問。 - 深入訪問節點 0 的相鄰未訪問節點
檢查節點 0 的相鄰節點,發現節點 1 是未訪問的,於是訪問節點 1,並標記它為已訪問。 - 繼續深入或回溯
檢查節點 1 的相鄰節點,發現節點 1 連接到的節點 2 已經被訪問,無其他未訪問節點,則回溯到節點 0,再回溯到節點 2。 - 結束搜尋
當回溯到節點 2 且所有相鄰節點都已訪問時,深度優先搜尋結束。
廣度優先搜尋 (Breadth-First Search, BFS)
在 BFS 中,從起點節點開始,逐層地擴展搜索,先探索所有與起點節點相鄰的節點,然後再逐層探索與這些節點相鄰的節點,以此類推。
BFS 使用一個稱為**佇列(Queue)**的資料結構來維護待處理的節點。
- 將起點節點放入佇列中。
- 從佇列中取出一個節點,將其標記為已訪問,並擴展搜索到該節點相鄰的未訪問節點,將這些節點加入佇列中。
重複這個過程,直到佇列中沒有未訪問的節點為止。
BFS 的特點是以廣度作為搜索的優先順序。也就是說,BFS 先搜索距離起點節點最近的節點,然後再搜索稍遠一些的節點。這意味著,在無權重圖(每條邊的成本都相同)上使用 BFS 搜索時,可以找到從起點到目標節點的最短路徑(如果存在);有權重的圖則要改用 Dijkstra 等演算法。
BFS 可以用在圖形算法、迷宮解決、最短路徑問題等。它確保在搜索過程中先處理較近的節點,因此通常用於在無權重圖中找尋最短路徑或最短距離。
| DFS | BFS | |
|---|---|---|
| 使用的資料結構 | Stack | Queue |
| 順序 | 不唯一 | 不唯一 |
為什麼走訪順序不唯一?
演算法的步驟是固定的,但演算法處理的對象(相鄰節點集合)是無序的。
以上面的例子來說,節點 2 的相鄰節點是 {0, 1, 3},DFS 只規定「選一個未訪問的相鄰節點繼續深入」,並沒有規定要先選哪一個,所以先走 0、1 或 3 都是合法的 DFS;BFS 把相鄰節點放入佇列的先後也是同樣的道理。
程式執行出來的結果會唯一,是因為我們在實作時依賴了特定的資料結構(如陣列或串列的排列順序),或加入了人為規則(如從小到大拜訪),而非 DFS/BFS 演算法本身限制只能有一種走訪順序。
例如上面的步驟先選了節點 3,走訪順序是 2 → 3 → 0 → 1;若規定從小到大拜訪,就會固定是 2 → 0 → 1 → 3。
雜湊函數 (Hash Function)
雜湊函數 (Hash Function) 是一種數學函數,它將任意大小的輸入數據(稱為資料)轉換為固定大小的輸出字串(稱為雜湊值)。
例如我們將 Hello World! 的字串分別用MD5、SHA1、SHA256
MD5: ed076287532e86365e841e92bfc50d8c
SHA1: 2ef7bde608ce5404e97d5f042f95f89f1c232871
SHA256: 7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069
- 雜湊函數會希望是不可逆
- 雜湊函數可能會有相同的情況(碰撞)
- 原始資料有小變動,則希望雜湊值更大的變化(Avalanche Effect)





