图数据结构 - 路径查找

import java.util.*;
/** * 使用邻接表存储图，并返回指定节点间的所有可能路径。 */public class DAGPaths {    private int V;    private Map<String, Integer> indexMap;    private Map<Integer, String> nameMap;    private List<Edge>[] adj;
    private static class Edge {        int to;        String weight;
        public Edge(int to, String weight) {            this.to = to;            this.weight = weight;        }    }
    public DAGPaths(int V) {        this.V = 0;        indexMap = new HashMap<>();        nameMap = new HashMap<>();        adj = new ArrayList[V];        for (int i = 0; i < V; i++) {            adj[i] = new ArrayList<Edge>();        }    }
    public void addEdge(String from, String to, String weight) {        BSTNode fromNode = findNode(from);        BSTNode toNode = findNode(to);        if (fromNode == null) {            fromNode = new BSTNode(from, V++);            indexMap.put(from, fromNode.index);            nameMap.put(fromNode.index, from);        }        if (toNode == null) {            toNode = new BSTNode(to, V++);            indexMap.put(to, toNode.index);            nameMap.put(toNode.index, to);        }        adj[fromNode.index].add(new Edge(toNode.index, weight));    }
    private BSTNode findNode(String name) {        int index = indexMap.getOrDefault(name, -1);        if (index == -1) {            return null;        }        return new BSTNode(name, index);    }
    public List<List<String>> getAllPaths(String start, String end) {        List<List<String>> paths = new ArrayList<>();        int startIdx = indexMap.getOrDefault(start, -1);        int endIdx = indexMap.getOrDefault(end, -1);        if (startIdx == -1 || endIdx == -1) {            return paths;        }        boolean[] visited = new boolean[V];        Stack<Integer> stack = new Stack<>();        stack.push(startIdx);        visited[startIdx] = true;        dfs(paths, stack, visited, endIdx);        return paths;    }
    private void dfs(List<List<String>> paths, Stack<Integer> stack, boolean[] visited, int end) {        int curr = stack.peek();        if (curr == end) {            List<String> path = new ArrayList<>();            for (int i : stack) {                path.add(nameMap.get(i));            }            paths.add(path);            return;        }        for (Edge e : adj[curr]) {            if (!visited[e.to]) {                stack.push(e.to);                visited[e.to] = true;                dfs(paths, stack, visited, end);                visited[e.to] = false;                stack.pop();            }        }    }
    private List<String> getWeight(List<String> path) {        List<String> weightList = new ArrayList<>();
        for(int left = 0; left < path.size() - 1; left++) {            int leftIndex = findNode(path.get(left + 1)).index;            String weight = adj[findNode(path.get(left)).index].stream().filter(e -> e.to == leftIndex).findFirst().get().weight;            weightList.add(weight);        }
        return weightList;    }
    private static class BSTNode {        String name;        int index;
        public BSTNode(String name, int index) {            this.name = name;            this.index = index;        }    }
    public static void main(String[] args) {        DAGPaths graph = new DAGPaths(8);        graph.addEdge("A", "B", "2");        graph.addEdge("A", "C", "3");        graph.addEdge("B", "D", "1");        graph.addEdge("C", "D", "5");        graph.addEdge("C", "E", "4");        graph.addEdge("D", "E", "1");        graph.addEdge("E", "F", "2");        graph.addEdge("E", "G", "3");        graph.addEdge("F", "H", "2");        graph.addEdge("G", "H","3");
        List<List<String>> paths = graph.getAllPaths("A", "H");        for (List<String> path : paths) {            System.out.println(path + " : " + graph.getWeight(path));        }    }}