Java生成树结构各点之间最短路径算法(Java实现树结构节点间最短路径算法)

原创

ithorizon 7个月前 (10-20) 阅读数 29 #后端开发

Java实现树结构节点间最短路径算法

一、引言

在计算机科学中，树是一种非常常见的数据结构，它由节点组成，每个节点包含数据和一个或多个指向子节点的指针。在许多应用场景中，我们需要找到树结构中两个节点之间的最短路径。本文将介绍怎样使用Java实现树结构节点间最短路径的算法。

二、树结构简介

树结构是一种非线性数据结构，它具有以下特点：

每个节点包含数据和一个或多个指向子节点的指针；

树结构具有唯一的根节点；

每个子节点最多只有一个父节点；

树结构中没有环。

三、最短路径算法原理

在树结构中，最短路径通常指的是两个节点之间经过的边数最少的路径。由于树结构没有环，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来找到两个节点之间的最短路径。

四、Java实现树结构节点间最短路径算法

下面我们将使用Java语言实现一个明了的树结构，并使用DFS算法来查找两个节点之间的最短路径。

4.1 定义树节点类

首先，我们需要定义一个树节点类，用于即树的节点：


public class TreeNode {
    int val; // 节点值
    List children; // 子节点列表
    public TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

4.2 实现DFS算法

接下来，我们实现一个DFS算法来查找两个节点之间的最短路径：


public class TreePathFinder {
    public static List findShortestPath(TreeNode root, TreeNode start, TreeNode end) {
        List path = new ArrayList<>();
        Map parentMap = new HashMap<>();
        dfs(root, start, end, parentMap);
        // 从终点回溯到起点
        TreeNode node = end;
        while (node != null) {
            path.add(node);
            node = parentMap.get(node);
        }
        // 反转路径
        Collections.reverse(path);
        return path;
    }
    private static boolean dfs(TreeNode node, TreeNode start, TreeNode end, Map parentMap) {
        if (node == null) {
            return false;
        }
        // 如果找到终点，返回true
        if (node == end) {
            return true;
        }
        // 遍历子节点
        for (TreeNode child : node.children) {
            parentMap.put(child, node);
            if (dfs(child, start, end, parentMap)) {
                return true;
            }
            parentMap.remove(child);
        }
        return false;
    }
}

4.3 测试算法

最后，我们编写一个测试类来验证算法的正确性：


public class Main {
    public static void main(String[] args) {
        // 构建树结构
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        root.children.add(node2);
        root.children.add(node3);
        node2.children.add(node4);
        node2.children.add(node5);
        node3.children.add(node6);
        // 查找最短路径
        List path = TreePathFinder.findShortestPath(root, node2, node6);
        // 输出路径
        for (TreeNode node : path) {
            System.out.print(node.val + " ");
        }
    }
}