深度优先搜索(DFS)和广度优先搜索(BFS)的区别及完整 Java 代码示例

DFS(深度优先搜索)和 BFS(广度优先搜索)是图和树结构中两种常见的遍历算法,它们各自具有不同的算法特点和适用场景。接下来我们将详细对比它们的原理、特点、应用场景,并提供更完整的 Java 代码实现,帮助你更好地理解和使用这两种算法。

一、深度优先搜索(DFS)

1. 定义
深度优先搜索(Depth First Search, DFS) 是从图或树的某个节点开始,沿着一条路径尽可能深入,直到无法再深入为止,然后回溯到上一个节点,继续寻找其他未访问的路径,直到遍历完所有节点为止。它优先访问深度较深的节点。

2. 特点

  • 递归或栈实现:DFS 常用递归实现,也可以用显式的栈模拟递归。
  • 路径优先:沿着一条路径一直深入直至叶子节点,然后回溯。
  • 内存占用少:因为 DFS 只需要记录当前路径,因此它比 BFS 占用更少的内存,尤其适合深度较大的图。
  • 可能陷入死循环:若图中存在环并且没有访问标记,则可能会陷入死循环,因此通常需要对访问过的节点进行标记。

3. 应用场景

  • 路径搜索问题:如查找图中从一个节点到另一个节点的所有路径。
  • 回溯问题:如八皇后问题、迷宫问题、数独等。
  • 连通性问题:检查图的连通性或分割成若干子图。

4. Java 实现 DFS

我们可以通过递归方式实现 DFS,也可以使用栈进行迭代实现。下面是使用递归实现的 Java 代码示例:

import java.util.*;

/**
 * @author 为一道彩虹
 */
public class DFSExample 
{
    // 深度优先搜索方法
    public static void dfs(Map<String, List<String>> graph, String node, Set<String> visited) 
    {
        // 如果节点已经访问过,则返回
        if (visited.contains(node))
        {
            return;
        }

        // 标记当前节点为已访问
        visited.add(node);
        System.out.print(node + " ");  // 输出当前节点

        // 递归访问所有相邻节点
        for (String neighbor : graph.get(node)) 
        {
            dfs(graph, neighbor, visited);
        }
    }

    public static void main(String[] args) 
    {
        // 定义一个图的邻接表表示法
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("D", "E"));
        graph.put("C", Arrays.asList("F"));
        graph.put("D", new ArrayList<>());
        graph.put("E", Arrays.asList("F"));
        graph.put("F", new ArrayList<>());

        // 用来记录访问过的节点
        Set<String> visited = new HashSet<>();

        System.out.println("深度优先搜索(DFS)遍历结果:");
        dfs(graph, "A", visited);  // 从节点 A 开始 DFS
    }
}
mathematica复制代码深度优先搜索(DFS)遍历结果:
A B D E F C

解释:从节点 A 开始,按照深度优先的方式进行遍历,访问完一条路径(例如 A -> B -> D -> E -> F),然后回溯到未访问的节点(C),直到所有节点遍历完毕。

6. DFS 的优点和缺点

  • 优点:

更适合搜索深层次的路径问题。

内存占用少,因为只需记录当前路径和访问的节点。

  • 缺点:

如果没有正确处理图中的环结构,可能会陷入无限递归,造成死循环。

在搜索广度较宽的图时效率不高

二、广度优先搜索(BFS)

1. 定义

广度优先搜索(Breadth First Search, BFS) 是从起点开始,优先访问当前节点的所有邻居节点,然后再访问这些邻居的邻居节点,依次向外层扩展,直到遍历完所有节点。它按层次逐层遍历。

2. 特点

  • 队列实现:BFS 通常用队列实现,首先将起始节点放入队列,依次弹出队列中的节点并访问其邻居。
  • 逐层扩展:BFS 按照广度逐层向外扩展,适合查找两点之间的最短路径。
  • 适合无权图的最短路径问题:由于 BFS 按层次访问,因此当某一节点首次被访问时,访问它的路径就是最短路径。

3. 应用场景

  • 最短路径问题:BFS 是解决无权图中最短路径问题的经典算法。
  • 层次遍历:适用于按层次遍历图或树。
  • 连通性问题:用于判断一个图是否是连通的,或者分割成多个连通子图。

4. Java 实现 BFS

BFS 依赖队列来实现,从起始节点开始,逐层扩展访问图中的节点。

import java.util.*;

/**
 * @author 为一道彩虹
 */
public class BFSExample 
{
    // 广度优先搜索方法
    public static void bfs(Map<String, List<String>> graph, String startNode) 
    {
        // 用于记录访问过的节点
        Set<String> visited = new HashSet<>();
        // 队列用于逐层遍历
        Queue<String> queue = new LinkedList<>();
        
        // 从起始节点开始
        queue.add(startNode);
        visited.add(startNode);
        
        while (!queue.isEmpty()) 
        {
            String node = queue.poll();  // 取出队列头部的节点
            System.out.print(node + " ");  // 输出当前节点
            
            // 将所有未访问过的邻居加入队列
            for (String neighbor : graph.get(node))
            {
                if (!visited.contains(neighbor)) 
                {
                    queue.add(neighbor);
                    visited.add(neighbor);  // 标记邻居为已访问
                }
            }
        }
    }

    public static void main(String[] args) 
    {
        // 定义一个图的邻接表表示法
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("D", "E"));
        graph.put("C", Arrays.asList("F"));
        graph.put("D", new ArrayList<>());
        graph.put("E", Arrays.asList("F"));
        graph.put("F", new ArrayList<>());

        System.out.println("广度优先搜索(BFS)遍历结果:");
        bfs(graph, "A");  // 从节点 A 开始 BFS
    }
}

5. 运行结果

mathematica复制代码广度优先搜索(BFS)遍历结果:
A B C D E F

解释:BFS 从节点 A 开始,先访问其邻居节点 B 和 C,接着依次访问 B 的邻居 D 和 E,C 的邻居 F,直到所有节点遍历完毕。

6. BFS 的优点和缺点

  • 优点:

BFS 是解决无权图最短路径问题的最佳选择。

它逐层扩展,适合用于层次遍历和连通性检查。

  • 缺点:

相比 DFS,占用的内存更多,因为 BFS 需要记录每层的所有节点。

在某些深度较大的图中,BFS 的效率可能较低。

三、DFS 与 BFS 的区别

特性

深度优先搜索(DFS)

广度优先搜索(BFS)

实现方式

递归或栈

队列

遍历方式

沿着路径尽量深入,直至没有未访问节点时回溯

按层次逐层遍历

适用场景

适用于查找路径、回溯问题、连通性检查

适用于查找无权图最短路径、层次遍历

优点

内存占用少,适合解决路径问题

可找到无权图中的最短路径

缺点

可能陷入死循环,需要显式防止重复访问

内存占用较大,可能在广度大的图中效率较低

空间复杂度

O(d),d 为图的深度

O(b^d),b 为每层的节点数,d 为图的深度

是否可找到最短路径

否(一般情况下)

是(适用于无权图)

四、总结

DFS:通过递归或栈实现,适合解决路径搜索和回溯问题,在图或树结构中优先深入进行遍历,直到无法再继续为止。

DFS 适合解决深度较深的路径问题,内存占用相对较少,但在环形结构中容易陷入死循环。

BFS:通过队列实现,逐层遍历图或树结构的节点,适用于无权图中的最短路径查找和层次遍历问题。

虽然 BFS 占用的内存较大,但它能有效找到两点间的最短路径。

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

区块链(Web3)开发工程师

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付:¥1
获取中
扫码支付

您的余额不足,请更换扫码支付或充值

打赏作者

实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值