---
tags: 演算法, LeetCode
disqus: HackMD
---

# 深度優先搜尋DFS

## 介紹

:::info
節點選項是用 **後進先出(LIFO)** 方式進行管理，所以可以使用堆疊的資料結構
:::


深度優先搜尋(DFS)演算法是一種遍歷圖形或樹形結構的方法，它會從起點開始遍歷，並儘可能深入每一個節點，直到找到目標節點或已經訪問過所有節點。在搜索過程中，`DFS` 會使用一個堆疊(Stack)來存儲所有還未訪問的節點。當一個節點被訪問時，它會被標記為已訪問，並將其相鄰的未訪問節點推入堆疊中，繼續遍歷直到找到目標節點或堆疊被清空。`DFS` 演算法容易實現，但可能會陷入無限循環或遍歷過多節點。

## 虛擬碼

以下是一個基本的深度優先搜尋演算法的範本:

function DFS(G, s) {
    const stack = [];
    stack.push(s);
    while (stack.length > 0) {
        const v = stack.pop();
        if (!G[v].visited) {
            G[v].visited = true;
            for (let u of G[v].adjacent) {
                stack.push(u);
            }
        }
    }
}

let G = {
    1: { visited: false, adjacent: [2, 3] },
    2: { visited: false, adjacent: [1, 4] },
    3: { visited: false, adjacent: [1, 4] },
    4: { visited: false, adjacent: [2, 3, 5] },
    5: { visited: false, adjacent: [4] }
};

DFS(G, 1);

G是一個圖形，s是起點。我們使用一個堆疊stack來存儲還未訪問的節點。
在遍歷過程中，如果一個節點v還沒有被訪問過，我們標記v為已訪問，然後將其相鄰的未訪問節點推入堆疊stack中。
我們重複這個過程，直到堆疊stack為空，即已經訪問過所有節點或者找到了目標節點。

## 複雜度

### 時間複雜度

$O(V+E)$
最壞情況下，DFS可以訪問所有節點和邊，因此時間複雜度為$O(V+E)$，其中`V`表示節點數，`E`表示邊數。

### 空間複雜度

$O(V)$
在最壞情況下，如果樹或圖是連通的，`DFS`可能會將整個樹或圖遍歷，因此空間複雜度為$O(V)$，其中`V`表示節點數。

如果使用遞歸實現`DFS`，那麼空間複雜度取決於堆疊(STACK)的最大深度，最壞情況下也是$O(V)$。

## 實戰

### 題目說明

給定一棵二元樹，找到它的最小深度。 最小深度是從根節點到最近的葉節點的最短路徑上的節點數。


### 解題

通過遞迴的方式進行深度優先搜索（DFS）來計算二元數的最小深度，並比較左子樹和右子樹的深度，最終返回二元樹的最小深度。

遞迴終止條件有三種情況：

1. 當 `root` 為 `null` 時，表示遍歷到了空節點，直接返回深度 0。
1. 當 `root` 的左子節點為 `null` 時，表示只有右子樹，繼續遞歸計算右子樹的最小深度，並加上當前節點，返回深度加 1。
1. 當 `root` 的右子節點為 `null` 時，表示只有左子樹，繼續遞歸計算左子樹的最小深度，並加上當前節點，返回深度加 1。

如果以上三種情況都不滿足，說明當前節點既有左子樹又有右子樹，此時取左子樹和右子樹的最小深度的較小值，並返回深度加 1 (當前節點)，即為最終的最小深度。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if (root == null) return 0;
    if (root.left == null) return minDepth(root.right) + 1
    if (root.right == null) return minDepth(root.left) + 1
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1
};