java树和图相关的算法:二叉树遍历、深度优先搜索、广度优先搜索等

简介: 树和图相关的算法:二叉树遍历、深度优先搜索、广度优先搜索等

在Java中,树和图相关的算法主要包括二叉树遍历、深度优先搜索(DFS)和广度优先搜索(BFS)。以下是这些算法的实现示例。

二叉树遍历

二叉树遍历有三种常见的方法:前序遍历(根节点 -> 左子树 -> 右子树)、中序遍历(左子树 -> 根节点 -> 右子树)和后序遍历(左子树 -> 右子树 -> 根节点)。

public class BinaryTree {
   
    static class TreeNode {
   
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
   
            val = x;
        }
    }

    public static void preOrderTraversal(TreeNode root) {
   
        if (root != null) {
   
            System.out.print(root.val + " ");
            preOrderTraversal(root.left);
            preOrderTraversal(root.right);
        }
    }

    public static void inOrderTraversal(TreeNode root) {
   
        if (root != null) {
   
            inOrderTraversal(root.left);
            System.out.print(root.val + " ");
            inOrderTraversal(root.right);
        }
    }

    public static void postOrderTraversal(TreeNode root) {
   
        if (root != null) {
   
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            System.out.print(root.val + " ");
        }
    }
}

深度优先搜索(DFS)

深度优先搜索是一种用于遍历或搜索树或图的算法。它通过递归地访问每个节点的所有后代来工作。

import java.util.*;

public class DFS {
   
    static class Node {
   
        int value;
        List<Node> neighbors;

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

    public static void dfs(Node node, Set<Node> visited) {
   
        if (node == null || visited.contains(node)) {
   
            return;
        }

        visited.add(node);

        System.out.println("Visiting: " + node.value);

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

在这个例子中,我们使用了一个简单的邻接列表表示图中的节点及其连接。dfs函数会递归地访问所有未被访问过的邻居节点。

广度优先搜索(BFS)

广度优先搜索是一种从一个节点开始,沿着最短路径访问所有可达节点的算法。通常使用队列来存储待访问的节点。

import java.util.*;

public class BFS {
   
    static class Node {
   
        int value;
        List<Node> neighbors;

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

    public static void bfs(Node node) {
   
        if (node == null) {
   
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()) {
   
            Node current = queue.poll();

            System.out.println("Visiting: " + current.value);

            for (Node neighbor : current.neighbors) {
   
                queue.offer(neighbor);
            }
        }
    }
}

在这个例子中,我们同样使用了一个简单的邻接列表表示图中的节点及其连接。bfs函数将从给定节点开始,按照宽度优先的顺序访问所有可达节点。

相关文章
|
20小时前
|
Java
Java二叉树超详解(常用方法介绍)(2)
Java二叉树超详解(常用方法介绍)(2)
|
20小时前
|
存储 Java
JAVA 二叉树超详解(1)
JAVA 二叉树超详解(1)
|
1天前
|
存储 算法 Java
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
6 0
|
1天前
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
5 0
|
3天前
|
机器学习/深度学习 算法 Java
递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】
递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】
25 1
|
4天前
|
存储 算法 安全
【国密算法】国密算法在Java中的实践
【国密算法】国密算法在Java中的实践
|
4天前
|
监控 算法 测试技术
【动态规划】【树形dp】【C++算法】968监控二叉树
【动态规划】【树形dp】【C++算法】968监控二叉树
|
4天前
|
算法 测试技术 C++
【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠
【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠
|
4天前
|
人工智能 算法 BI
【深度优先搜索】【C++算法】834 树中距离之和
【深度优先搜索】【C++算法】834 树中距离之和
|
8天前
|
存储 算法 搜索推荐
Java中的数据结构与算法解析
Java中的数据结构与算法解析

相关产品