java深度遍历寻找最小路径

你可以使用深度优先搜索（DFS）算法来进行深度遍历并找到最小路径。下面是一个使用Java实现DFS的示例代码，其中包括寻找最小路径的部分：

import java.util.ArrayList;
import java.util.List;

public class MinimumPathDFS {

    private int minPath;  // 最小路径长度
    private List<Integer> minPathNodes;  // 最小路径节点列表

    public List<Integer> findMinimumPath(int[][] graph, int start, int end) {
        minPath = Integer.MAX_VALUE;
        minPathNodes = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[graph.length];
        dfs(graph, start, end, 0, path, visited);
        return minPathNodes;
    }

    private void dfs(int[][] graph, int current, int end, int pathLen, List<Integer> path, boolean[] visited) {
        path.add(current);
        visited[current] = true;

        if (current == end) {
            if (pathLen < minPath) {
                minPath = pathLen;
                minPathNodes.clear();
                minPathNodes.addAll(path);
            }
        } else {
            for (int i = 0; i < graph[current].length; i++) {
                if (graph[current][i] != 0 && !visited[i]) {
                    dfs(graph, i, end, pathLen + graph[current][i], path, visited);
                }
            }
        }

        path.remove(path.size() - 1);
        visited[current] = false;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 4, 0, 0},
            {0, 0, 3, 2, 0},
            {0, 0, 0, 0, 2},
            {0, 0, 0, 0, 3},
            {0, 0, 0, 0, 0}
        };
        int start = 0;
        int end = 4;

        MinimumPathDFS solver = new MinimumPathDFS();
        List<Integer> minPathNodes = solver.findMinimumPath(graph, start, end);

        if (minPathNodes.isEmpty()) {
            System.out.println("No path found!");
        } else {
            System.out.println("Minimum path: " + minPathNodes);
            System.out.println("Minimum path length: " + (solver.minPath - graph[start][end]));
        }
    }
}

在上面的示例中，我们通过传入一个邻接矩阵 `graph`、起始节点 `start` 和目标节点 `end` 来调用 `findMinimumPath` 方法，它会返回最小路径上的节点列表。

请注意，这只是一个简单的示例，假设节点之间的路径长度都是非负整数。如果图中存在负权边，则需要使用其他算法，如Dijkstra算法或Bellman-Ford算法。