迭代替代递归：使用队列进行广度优先搜索，避免栈溢出

图的广度优先搜索

使用迭代方式进行广度优先搜索

使用迭代方式进行广度优先搜索（BFS）是一个常见的技术，尤其是在需要避免递归栈深度限制的情况下。广度优先搜索天然就是一种迭代方法，因为它利用了队列来管理节点的访问顺序。

import java.util.*;

public class BFSExample {

    // 方法：执行广度优先搜索
    public static void bfs(Map<String, List<String>> graph, String start) {
        // 创建一个队列来存储待访问的节点
        Queue<String> queue = new LinkedList<>();
        // 创建一个集合来存储已访问的节点
        Set<String> visited = new HashSet<>();

        // 将起始节点添加到队列并标记为访问过
        queue.add(start);
        visited.add(start);

        // 当队列不为空时循环
        while (!queue.isEmpty()) {
            // 从队列中取出一个节点
            String node = queue.poll();
            System.out.println("Visited: " + node); // 处理节点（此处为打印节点）

            // 获取当前节点的所有邻居
            List<String> neighbors = graph.get(node);
            if (neighbors != null) {
                for (String neighbor : neighbors) {
                    // 如果邻居没有访问过，将其加入队列和已访问集合
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.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("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));

        // 从节点 'A' 开始执行广度优先搜索
        bfs(graph, "A");
    }
}

代码说明

  1. 数据结构：

    • Queue<String> queue = new LinkedList<>();：使用 LinkedList 实现 Queue 接口，用于管理BFS的节点。

    • Set<String> visited = new HashSet<>();：使用 HashSet 追踪已经访问过的节点，防止重复访问。

  2. 主逻辑：

    • 起始节点被添加到队列，并标记为已访问。

    • 在 while 循环中，持续从队列中取出节点进行处理。

    • 对于每一个节点，将其所有未访问过的邻居节点加入队列，并标记为已访问。

  3. 避免递归：

    • 该方法完全基于迭代过程，没有递归调用，因此也就没有栈深度限制的问题，非常适合大规模图的遍历。

这种方法能有效地处理大型数据集，是替代深度优先搜索（DFS）递归实现的一种稳健方法。

树的广度优先搜索

定义 TreeNode 类来表示树的节点

import java.util.*;

class TreeNode {
    String value;
    List<TreeNode> children;

    TreeNode(String value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    void addChild(TreeNode child) {
        this.children.add(child);
    }
}

实现一个方法来进行BFS遍历

public class TreeBFS {

    // 广度优先搜索方法
    public static void bfs(TreeNode root) {
        if (root == null) return;

        // 使用队列来存储待访问的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            // 从队列中取出一个节点
            TreeNode current = queue.poll();
            System.out.println("Visited: " + current.value);

            // 将当前节点的所有子节点加入队列
            for (TreeNode child : current.children) {
                queue.add(child);
            }
        }
    }

    public static void main(String[] args) {
        // 创建树的节点
        TreeNode root = new TreeNode("A");
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");

        // 构建树结构
        root.addChild(nodeB);
        root.addChild(nodeC);
        nodeB.addChild(nodeD);
        nodeB.addChild(nodeE);
        nodeC.addChild(nodeF);

        // 执行广度优先搜索
        bfs(root);
    }
}

代码说明

  1. TreeNode 类:

    • 每个节点有一个 value 表示节点的值，和一个 children 列表来存储子节点。

    • addChild 方法用于向当前节点添加子节点。

  2. BFS 方法:

    • 将起始节点（根节点）放入队列。

    • 使用 while 循环遍历队列中的节点。

    • 对于每个节点，打印其值并将其所有子节点加入队列。

  3. 树结构:

    • 在 main 方法中，创建树的节点并建立父子关系。

    • 从根节点开始调用 bfs 方法进行遍历。

这样，你可以遍历树中的所有节点，并按层次顺序访问它们。这种方法避免了递归的潜在栈溢出问题，非常适合用于处理可能非常大的树结构。

使用栈进行深度优先搜索

在经典的算法实现中，队列通常用于广度优先搜索（BFS），而栈用于深度优先搜索（DFS）。然而，你可以使用队列来模拟DFS，但这并不是常见的做法，因为它不符合队列先进先出的特性。

使用队列进行深度优先搜索

虽然不是很常规，但你确实可以用队列来模拟DFS。这可以通过在队列中插入节点时将其邻居逆序插入实现，以便在后续处理时仍能先访问最后加入的节点。这种方法可以实现，但并不直观，代码复杂性增加，而且违背了使用队列的常规用途。

图使用栈进行深度优先搜索

DFS通常使用栈来实现

import java.util.*;

public class GraphDFSIterative {

    // 深度优先搜索的迭代方法
    public static void dfs(Map<String, List<String>> graph, String start) {
        Stack<String> stack = new Stack<>();
        Set<String> visited = new HashSet<>();

        stack.push(start);

        while (!stack.isEmpty()) {
            String node = stack.pop();

            if (!visited.contains(node)) {
                System.out.println("Visited: " + node);
                visited.add(node);

                // 将邻居节点逆序压入栈中
                List<String> neighbors = graph.get(node);
                if (neighbors != null) {
                    for (int i = neighbors.size() - 1; i >= 0; i--) {
                        String neighbor = neighbors.get(i);
                        if (!visited.contains(neighbor)) {
                            stack.push(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("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));

        dfs(graph, "A");
    }
}

树使用栈进行深度优先搜索

使用栈来进行深度优先搜索（DFS）遍历树结构

import java.util.*;

class TreeNode {
    String value;
    List<TreeNode> children;

    TreeNode(String value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    void addChild(TreeNode child) {
        this.children.add(child);
    }
}

public class TreeDFSIterative {

    // 深度优先搜索的迭代方法
    public static void dfs(TreeNode root) {
        if (root == null) return;

        // 使用栈来存储待访问的节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            // 从栈中弹出一个节点
            TreeNode current = stack.pop();
            System.out.println("Visited: " + current.value); // 处理当前节点

            // 将当前节点的子节点逆序压入栈中
            List<TreeNode> children = current.children;
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
        }
    }

    public static void main(String[] args) {
        // 创建树的节点
        TreeNode root = new TreeNode("A");
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");

        // 构建树结构
        root.addChild(nodeB);
        root.addChild(nodeC);
        nodeB.addChild(nodeD);
        nodeB.addChild(nodeE);
        nodeC.addChild(nodeF);

        // 执行深度优先搜索
        dfs(root);
    }
}

比较

  1. 使用目的：

    • 队列用于BFS：自然符合逻辑顺序（FIFO），逐层访问节点。

    • 栈用于DFS：自然符合深度优先逻辑（LIFO），先深入再扩展。

  2. 直观性和效率：

    • 使用队列进行BFS和使用栈进行DFS都是直观的，符合数据结构的特性。

    • 使用队列来模拟DFS不符合队列的FIFO特性，并且会使代码复杂性增加，效率降低。

  3. 避免递归：

    • 这两种迭代实现都能避免递归调用引起的栈溢出问题。因此，选择使用栈来实现DFS迭代遍历更合适。

总的来说，使用队列进行BFS和使用栈进行DFS是最佳实践，符合各自的数据结构特性和算法目的。如果想避免递归，使用栈来实现DFS是一种正确且直接的做法。

树的递归遍历

对于树的遍历，我们通常使用深度优先搜索（DFS）的方式，如前序遍历。以下是如何用递归实现树的遍历

import java.util.*;

class TreeNode {
    String value;
    List<TreeNode> children;

    TreeNode(String value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    void addChild(TreeNode child) {
        this.children.add(child);
    }
}

public class TreeDFS {

    // 深度优先搜索的递归方法
    public static void dfs(TreeNode node) {
        if (node == null) return;

        System.out.println("Visited: " + node.value);  // 处理当前节点

        // 遍历每一个子节点
        for (TreeNode child : node.children) {
            dfs(child);  // 递归调用
        }
    }

    public static void main(String[] args) {
        // 创建树的节点
        TreeNode root = new TreeNode("A");
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");

        // 构建树结构
        root.addChild(nodeB);
        root.addChild(nodeC);
        nodeB.addChild(nodeD);
        nodeB.addChild(nodeE);
        nodeC.addChild(nodeF);

        // 执行深度优先搜索
        dfs(root);
    }
}

图的递归遍历

对于图的遍历，递归实现通常使用深度优先搜索（DFS）。在图中，由于可能存在环，我们需要一个集合来记录访问过的节点，以防止无限递归。

import java.util.*;

public class GraphDFS {

    // 深度优先搜索的递归方法
    public static void dfs(Map<String, List<String>> graph, String node, Set<String> visited) {
        if (visited.contains(node)) return;

        System.out.println("Visited: " + node);  // 处理当前节点
        visited.add(node);

        // 遍历邻居节点
        List<String> neighbors = graph.get(node);
        if (neighbors != null) {
            for (String neighbor : neighbors) {
                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("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));

        // 执行深度优先搜索
        Set<String> visited = new HashSet<>();
        dfs(graph, "A", visited);
    }
}

0
  • ©2024-2025 秋之牧云. Halo
  • 陇ICP备2024006552号-1
    • About Me

    Hometown：MinXian, Gansu

    Follow Me
    听我一言
      232025/02

      错的不是我，而是这个世界！

    站点统计
    • 文章78
    • 片刻25
    • 留言8
    • 标签44
    • 分类8
    • 运营2024-01-28
  • 动态
  • 文章
  • 图库
  • 音乐

    • 加载中..

    作者..
    00:00
    /
    00:00
    消息盒子

    # 暂无消息 #

    只显示最新10条未读和已读信息

    创建
    • 日常
    • 一路拍摄
    |
    确定
    位置已开启
    😃😊😉😒😘👌👍💖💋👏😂😜✌🎁☕🌹🤦👀😆🤢😈👻🙊😥😶😐😤😱🙏💪
    从媒体库选择
    插入图床图片
    控制台 登出