/**
 * 作者 : Siddhant Swarup Mallick
 * Github : https://github.com/siddhant2002
 */

/** 程序描述 - 查找从源点到目的地的所有可能路径 */

/** 维基百科链接 -> https://en.wikipedia.org/wiki/Shortest_path_problem */
package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

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

public class AllPathsFromSourceToTarget {

    // 图中的顶点数量
    private final int v;

    // 存储从源点到目的地的路径
    static List<List<Integer>> nm = new ArrayList<>();
    // 邻接表
    private ArrayList<Integer>[] adjList;

    // 构造函数
    public AllPathsFromSourceToTarget(int vertices) {

        // 初始化顶点数量
        this.v = vertices;

        // 初始化邻接表
        initAdjList();
    }

    // 初始化邻接表的工具方法
    private void initAdjList() {
        adjList = new ArrayList[v];

        for (int i = 0; i < v; i++) {
            adjList[i] = new ArrayList<>();
        }
    }

    // 添加从 u 到 v 的边
    public void addEdge(int u, int v) {
        // 将 v 添加到 u 的列表中。
        adjList[u].add(v);
    }

    // 存储所有路径
    public void storeAllPaths(int s, int d) {
        boolean[] isVisited = new boolean[v];
        ArrayList<Integer> pathList = new ArrayList<>();

        // 将源点添加到路径中
        pathList.add(s);
        // 调用递归工具
        storeAllPathsUtil(s, d, isVisited, pathList);
    }

    // 一个递归函数，用于打印从 'u' 到 'd' 的所有路径。
    // isVisited[] 跟踪当前路径中的顶点。
    // localPathList<> 存储当前路径中的实际顶点
    private void storeAllPathsUtil(Integer u, Integer d, boolean[] isVisited, List<Integer> localPathList) {

        // 如果到达目的地
        if (u.equals(d)) {
            nm.add(new ArrayList<>(localPathList));
            return;
        }

        // 标记当前节点
        isVisited[u] = true;

        // 对当前顶点相邻的所有顶点进行递归

        for (Integer i : adjList[u]) {
            if (!isVisited[i]) {
                // 将当前节点存储在路径中
                localPathList.add(i);
                storeAllPathsUtil(i, d, isVisited, localPathList);

                // 从路径中移除当前节点
                localPathList.remove(i);
            }
        }

        // 取消标记当前节点
        isVisited[u] = false;
    }

    // 驱动程序
    public static List<List<Integer>> allPathsFromSourceToTarget(int vertices, int[][] a, int source, int destination) {
        // 创建一个示例图
        AllPathsFromSourceToTarget g = new AllPathsFromSourceToTarget(vertices);
        for (int[] i : a) {
            g.addEdge(i[0], i[1]);
            // 添加边
        }
        g.storeAllPaths(source, destination);
        // 调用方法存储所有可能的路径
        return nm;
        // 返回从源点到目的地的所有可能路径
    }
}
