通过两点获取全部路径(string) && Return all paths from a given source to a destination(string) #14

// A directed graph using 
// adjacency map representation
public class Graph {

    // No. of vertices in graph 
    private String s;

    // adjacency list  
    private Map<String, List<String>> adjMap;

    private List<List<String>> resultList;

    //Constructor
    public Graph(Map<String, List<String>> nodeMap){
        if (Objects.isNull(nodeMap)) {
            throw new NullPointerException("node map is not be null!");
        }
        this.adjMap = nodeMap;
        this.resultList = new ArrayList<>();
    }

    // Get all paths from
    // 's' to 'd' 
    public List<List<String>> getAllPaths(String s, String d) {
        if (Objects.isNull(s) || Objects.isNull(d)) {
            throw new NullPointerException("source or destination must not be null");
        }

        if (Objects.isNull(this.s)) {
            this.s = s;
        }

        Map<String, Boolean> isVisited = new HashMap<>(adjMap.size());
        List<String> pathList = new ArrayList<>();

        // add source to pathList
        pathList.add(s);

        // Call recursive utility
        getAllPathsUtil(s, d, isVisited, pathList);

        return this.resultList;
    }

    // A recursive function to print 
    // all paths from 'u' to 'd'. 
    // isVisited map keeps track of
    // vertices in current path. 
    // localPathList<> stores actual 
    // vertices in the current path 
    private void getAllPathsUtil(String u, String d,
                                   Map<String, Boolean> isVisited,
                                   List<String> localPathList) {

        // Mark the current node
        isVisited.put(u, Boolean.TRUE);

        if (u.equals(d)) {
            resultList.add(new ArrayList<>(localPathList));
            System.out.println(localPathList); // print one finished path
            // if match found then no need to traverse more till depth 
            isVisited.put(u, Boolean.FALSE);
            return;
        }

        // Recur for all the vertices 
        // adjacent to current vertex
        List<String> vertices = adjMap.get(u);

        for (String i : vertices) {
            if (Objects.isNull(isVisited.get(i)) || !isVisited.get(i)) {
                // store current node  
                // in path list
                localPathList.add(i);
                getAllPathsUtil(i, d, isVisited, localPathList);

                // remove current node 
                // in path list
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited.put(u, Boolean.FALSE);
    }

}

public class Demo {
    public static void main(String[] args) {
        Map<String, List<String>> nodeMap = new HashMap<>();
        nodeMap.put("0", Arrays.asList("1", "3"));
        nodeMap.put("1", Arrays.asList("0", "2"));
        nodeMap.put("2", Arrays.asList("1", "3", "4"));
        nodeMap.put("3", Arrays.asList("0", "2", "4"));
        nodeMap.put("4", Arrays.asList("2", "3"));

        List<List<String>> allPaths = new Graph(nodeMap).getAllPaths("2", "4");
        System.out.println(allPaths); // print [[2, 1, 0, 3, 4], [2, 3, 4], [2, 4]]
    }
}