深度优先与广度优先Java实现代码示例

下面我来详细讲解一下“深度优先与广度优先Java实现代码示例”的攻略。

一、深度优先搜索

1. 简介

深度优先搜索（DFS）是一种经典的搜索方法，其基本思想是从一个起始状态开始，尽可能地遍历尽每一个可能到达的状态，直到搜索完所有的状态或者找到了一个目标状态。

2. 实现代码示例

下面是一个简单的深度优先搜索的Java实现代码示例：

public void dfs(Node node) {
    if (node == null) {
        return;
    }
    System.out.println(node.value);
    node.visited = true;
    for (Node child : node.children) {
        if (!child.visited) {
            dfs(child);
        }
    }
}

该代码中，dfs()方法接收一个Node类型的参数node作为起始状态，然后对node进行遍历，输出该节点的值，并将其visited属性设为true。接着遍历node的所有未访问的子节点，对未访问的子节点递归调用dfs()方法。

二、广度优先搜索

1. 简介

广度优先搜索（BFS）也是一种常见的搜索算法，与深度优先搜索不同的是，BFS从起始状态开始，逐步向外进行搜索，先搜索到的节点一定是离起始节点最近的，后搜索到的节点一定离起始节点更远。

2. 实现代码示例

下面是一个简单的广度优先搜索的Java实现代码示例：

public void bfs(Node node) {
    if (node == null) {
        return;
    }
    Queue<Node> q = new LinkedList<Node>();
    q.offer(node);
    node.visited = true;
    while (!q.isEmpty()) {
        Node n = q.poll();
        System.out.println(n.value);
        for (Node child : n.children) {
            if (!child.visited) {
                q.offer(child);
                child.visited = true;
            }
        }
    }
}

该代码中，bfs()方法同样接收一个Node类型的参数node作为起始状态，首先将node加入一个队列q中。接着进行循环，从队列中取出一个节点n并输出其值，然后将n的所有未访问的子节点加入队列中。值得注意的是，在将子节点加入队列之前，还需要将其visited属性设为true，避免重复访问。

三、示例说明

以一个二叉树为例，来说明深度优先搜索和广度优先搜索的实现。

1. 二叉树结构

我们定义一个二叉树的Node类，其结构如下：

class Node {
    public int value;
    public Node left;
    public Node right;
    public boolean visited;
}

其中，value表示节点的值，left和right分别表示该节点的左右子节点，visited表示该节点是否已被访问过。

假设我们有如下的一棵二叉树：

     5
   /   \
  3     8
 / \   / \
2   4 7   9

2. 深度优先搜索示例

对上述二叉树进行深度优先搜索，我们可以按照先序遍历的顺序，从根节点开始遍历，输出5、3、2、4、8、7、9，代码如下：

public void dfs(Node node) {
    if (node == null) {
        return;
    }
    System.out.println(node.value);
    node.visited = true;
    if (node.left != null && !node.left.visited) {
        dfs(node.left);
    }
    if (node.right != null && !node.right.visited) {
        dfs(node.right);
    }
}

3. 广度优先搜索示例

对上述二叉树进行广度优先搜索，我们需要用一个队列来存储每一层的节点，从根节点开始，输出5、3、8、2、4、7、9，代码如下：

public void bfs(Node node) {
    if (node == null) {
        return;
    }
    Queue<Node> q = new LinkedList<Node>();
    q.offer(node);
    node.visited = true;
    while (!q.isEmpty()) {
        Node n = q.poll();
        System.out.println(n.value);
        if (n.left != null && !n.left.visited) {
            q.offer(n.left);
            n.left.visited = true;
        }
        if (n.right != null && !n.right.visited) {
            q.offer(n.right);
            n.right.visited = true;
        }
    }
}

以上是“深度优先与广度优先Java实现代码示例”的完整攻略，希望能对你有所帮助。