import java.util.*;

// 单源路径
public class SingleSourcePath {
    private Graph G;
    private int s;
    private boolean[] visited;
    private int[] pre;  //上一个点


    public SingleSourcePath(Graph G , int s){
        G.validateVertex(s);
        this.G = G;
        this.s = s; // 原点
        visited = new boolean[G.V()];
        pre = new int[G.V()];

        for(int i=0;i<pre.length;i++)
            pre[i] = -1;

        //dfs(s,s);
        bfs(s);
    }

    // 深度优先遍历
    private void dfs(int v,int parent){
        visited[v] = true;
        pre[v] = parent;
        // 遍历相邻节点
        for(int w : G.adj(v)){
            if(!visited[w])
                dfs(w,v);
        }
    }

    // 广度优先遍历
    private void bfs(int s){
        Queue<Integer> queue = new LinkedList<>();  // LinkedList 实现了queue接口

        // 入队并标记访问
        queue.add(s);
        visited[s] = true;
        pre[s] = s;

        while(!queue.isEmpty()){
            int v = queue.remove(); //从队列取出元素
            for(int w:G.adj(v)){
                if(!visited[w]) {
                    // 入队并标记访问
                    queue.add(w);
                    visited[w] = true;
                    pre[w] = v;
                }
            }
        }
    }

    // 从源到目标是否可以连接
    public boolean isConnectedTo(int t){
        G.validateVertex(t);
        return visited[t];
    }

    // 从源到目标的路径
    public Iterable<Integer> path(int t){
        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur]; // 上一个节点
        }
        res.add(s);
        Collections.reverse(res);   // 反
        return res;
    }


    public static void main(String[] args){

        Graph g = new Graph("g.txt");
        SingleSourcePath singleSourcePath = new SingleSourcePath(g,0);
        System.out.println(singleSourcePath.path(6));
    }
}