深度优先搜索

深度优先搜索 Depth First Search

如上图所示，从 $1$ 号节点到 $5$ 号节点共有四条路径，每条路径和其分别耗时如下：

1. $1\to 2\to 5$，耗时 $2 + 16 = 18$ 分钟。
2. $1\to 2\to 3\to 5$，耗时 $2 + 7 + 5 = 14$ 分钟。
3. $1\to 4\to 5$，耗时 $6 + 12 = 18$ 分钟。
4. $1 \to 4\to 3\to 5$，耗时 $6 + 6 + 5 = 17$ 分钟。

其中第二个方案是最优解，耗时 $14$ 分钟。因此，一个可行的算法方案是使用深度优先搜索暴力枚举出所有可行的路径并记录最小值即可，其代码实现如下：

// ans 用于记录答案，一开始把答案设置为无穷大。
int ans = 0x7f7f7f7f;
// 记录一个点是否被访问过，防止出现循环。
int vis[105];
struct Edge{
    int to;
    int weight;
}; vector<Edge> G[105];

// 表示到 node 节点的耗时为 steps。
void dfs(int node, int steps){
    if (steps >= ans) // 最优性剪枝。
    // 如果走到目标答案，就更新结果并返回。
    if (node == terminal){
        ans = min(ans, steps);
        return ;
    }
	for (Edge next : G[node]){
        // 遍历从 node 开始所有的边。
        if (vis[next.to]) continue ;  // 被访问过了，就跳过。
    	vis[next.to] = 1;  // 将节点标记为已访问的状态。
        dfs(next.to, steps + next.weight);  // 继续递归。
        vis[next.to] = 0;  // 将节点标记为未访问的状态。
    }
    return ;
}

深度有优先搜索算法虽然很有效，但是该算法的运行效率太低下了，只适用于数据量较小的情况。假设图是一个二叉树树形结构，那么在最坏的情况下，这个算法的时间复杂度将会达到 $O(2^N)$。当每个顶点的度越多，深度优先搜索算法的时间复杂度就高。因此，在一般情况下，我们不会使用深度优先搜索。

设想在二维 $N \times M$ 地图问题的情况下，我们怎么找到从入口到出口的最佳路径？一般情况下，我们会使用广度优先搜索的算法。广度优先搜索算法的复杂度远远低于深度优先搜索。