欢迎访问宙启技术站
智能推送

使用Java函数实现图的深度优先搜索(DFS)和广度优先搜索(BFS)。

发布时间:2023-07-02 09:19:32

深度优先搜索(DFS)和广度优先搜索(BFS)都是图的遍历算法,用于遍历图中的节点。下面是使用Java函数实现DFS和BFS的示例代码。

深度优先搜索(DFS):

import java.util.*;

// 图的节点类
class Node {
    int value;
    List<Node> neighbors;

    public Node(int value) {
        this.value = value;
        this.neighbors = new ArrayList<>();
    }
}

public class DFS {
    // DFS遍历函数
    public static void dfs(Node node, Set<Node> visited) {
        System.out.print(node.value + " ");
        visited.add(node);

        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        // 创建图
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        // 构建图的关系
        node1.neighbors.add(node2);
        node1.neighbors.add(node3);
        node2.neighbors.add(node4);

        // 创建访问集合
        Set<Node> visited = new HashSet<>();

        // 调用DFS函数
        dfs(node1, visited);
    }
}

输出结果:1 2 4 3

广度优先搜索(BFS):

import java.util.*;

// 图的节点类
class Node {
    int value;
    List<Node> neighbors;

    public Node(int value) {
        this.value = value;
        this.neighbors = new ArrayList<>();
    }
}

public class BFS {
    // BFS遍历函数
    public static void bfs(Node node) {
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visited = new HashSet<>();

        queue.offer(node);
        visited.add(node);

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            System.out.print(currentNode.value + " ");

            for (Node neighbor : currentNode.neighbors) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 创建图
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        // 构建图的关系
        node1.neighbors.add(node2);
        node1.neighbors.add(node3);
        node2.neighbors.add(node4);

        // 调用BFS函数
        bfs(node1);
    }
}

输出结果:1 2 3 4

以上是DFS和BFS的简单实现示例,通过创建图的节点对象和建立节点之间的连接关系,然后使用DFS和BFS函数进行遍历。在遍历过程中使用Set集合来记录访问过的节点,保证节点不会被重复访问。