常用的搜索算法之深度优先搜索

jack.yang

发布于 2025-04-05 17:11:47

5480

深度优先搜索（DFS）原理

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。该算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

优缺点

优点：

空间复杂度较低：相比广度优先搜索（BFS），DFS通常只需要较少的内存空间，因为它不需要存储所有待访问的节点。
代码实现简单：DFS的递归实现通常比BFS的迭代实现更为直观和简洁。

缺点：

时间复杂度可能较高：对于某些图，DFS可能需要更长的时间才能访问所有节点，因为它会深入搜索一个分支直到无法继续，然后再回溯。
不适用于寻找最短路径：DFS通常不会找到从源点到目标点的最短路径，因为它不是基于距离的搜索。

使用场景

图的连通性问题：DFS可以用来判断图是否连通，或者找出图中的所有连通分量。
拓扑排序：在有向无环图（DAG）中，DFS可以用来进行拓扑排序。
寻找强连通分量：在有向图中，DFS可以用来找出所有的强连通分量。
解决迷宫问题：在迷宫问题中，DFS可以用来搜索所有可能的路径，找到从起点到终点的路径。
搜索问题：DFS也可以用于各种搜索问题，如树的搜索、图的搜索等。

常用算法

虽然DFS本身是一个算法，但有一些基于DFS的常用算法和变体：

回溯算法：回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些更改来丢弃该解，即“回溯”并尝试其他可能的解。回溯算法通常使用DFS来实现。
图的着色问题：在图的m着色问题中，需要给图的每个顶点分配一种颜色，使得相邻的顶点颜色不同。这个问题可以使用DFS和回溯算法来解决。
旅行商问题（TSP）的近似解：虽然TSP是一个NP-hard问题，但DFS可以用于找到其近似解或某些特定情况下的解。
八数码问题（滑动拼图）：这是一个经典的搜索问题，目标是将一个乱序的3x3数字拼图滑动到正确的位置。DFS可以用来搜索所有可能的移动序列。
求解迷宫问题：在迷宫问题中，DFS可以用来搜索所有可能的路径，找到从起点到终点的路径。这通常与回溯算法结合使用，以便在发现死路时能够回溯并尝试其他路径。

Java代码示例

以下是使用Java语言编写的深度优先搜索（DFS）的示例代码，该代码适用于无向图：

首先，我们需要定义一个表示图的类，这里我们使用邻接列表来表示图：

import java.util.*;  
  
class Graph {  
    private int V; // 顶点数量  
    private LinkedList<Integer> adj[]; // 邻接列表  
  
    // 构造函数  
    Graph(int v) {  
        V = v;  
        adj = new LinkedList[v];  
        for (int i=0; i<v; ++i)  
            adj[i] = new LinkedList();  
    }  
  
    // 添加边  
    void addEdge(int v, int w) {  
        adj[v].add(w);  
        // 因为是无向图，所以也要添加反向边  
        adj[w].add(v);  
    }  
  
    // DFS遍历  
    void DFS(int v, boolean visited[]) {  
        // 标记当前节点为已访问  
        visited[v] = true;  
        System.out.print(v+" ");  
  
        // 递归访问所有未访问的邻居节点  
        Iterator<Integer> i = adj[v].listIterator();  
        while (i.hasNext()) {  
            int n = i.next();  
            if (!visited[n])  
                DFS(n, visited);  
        }  
    }  
  
    // DFS遍历的入口函数  
    void DFS(int v) {  
        boolean visited[] = new boolean[V];  
  
        // 调用递归函数进行DFS遍历  
        DFS(v, visited);  
    }  
}  
  
// 主类  
public class Main {  
    public static void main(String args[]) {  
        // 创建一个图，包含5个顶点  
        Graph g = new Graph(5);  
  
        g.addEdge(0, 1);  
        g.addEdge(0, 4);  
        g.addEdge(1, 2);  
        g.addEdge(1, 3);  
        g.addEdge(1, 4);  
        g.addEdge(2, 3);  
        g.addEdge(3, 4);  
  
        System.out.println("Depth First Traversal (starting from vertex 0):");  
  
        // 从顶点0开始进行DFS遍历  
        g.DFS(0);  
    }  
}

在上面的代码中，Graph 类用于表示一个图，并且实现了 addEdge 方法来添加边和 DFS 方法来进行深度优先搜索。主函数 main 中创建了一个 Graph 对象并添加了边，然后调用 DFS 方法从顶点0开始进行深度优先遍历。

运行上述代码，你将看到从顶点0开始的深度优先遍历结果。在这个例子中，输出将是 0 1 4 3 2（遍历的顺序可能因具体实现和图的结构而有所不同，但会访问所有节点一次）。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除

算法