package Graph;
import java.util.ArrayList;
import java.util.*;

public class GraphTraversal {
    public  static  class  Edge{
        int src;
        int dest;
        Edge(int src , int dest){
            this.dest=dest;
            this.src =src;
        }
    }
    static void creategraph(ArrayList<Edge> g []){
        for(int i=0;i<g.length;i++){
            g[i] = new ArrayList<>();
        }
        g[0].add(new Edge(0,1));
        g[0].add(new Edge(0,2));

        g[1].add(new Edge(1,0));
        g[1].add(new Edge(1,3));

        g[2].add(new Edge(2,0));
        g[2].add(new Edge(2,4));

        g[3].add(new Edge(3,1));
        g[3].add(new Edge(3,4));
        g[3].add(new Edge(3,5));

        g[4].add(new Edge(4,2));
        g[4].add(new Edge(4,3));
        g[4].add(new Edge(4,5));

        g[5].add(new Edge(5,3));
        g[5].add(new Edge(5,4));
        g[5].add(new Edge(5,6));

        g[6].add(new Edge(6,5));
    }


    //DFS Traversal
    public static void dfs(ArrayList<Edge> list[], boolean[] visited, int curr){
       if(visited[curr]){
           return;
       }
        System.out.println(curr);
       visited[curr] = true;
       for(int i=0;i<list[curr].size();i++){
           Edge e = list[curr].get(i);
           dfs(list,visited,e.dest);
       }
    }

    //BFS Traversal
    public static void bfs(ArrayList<Edge> list[]){
       Queue<Integer> q = new LinkedList<>();
       boolean visited[] = new boolean[list.length];

       q.add(0);

       while(!q.isEmpty()){
           int curr = q.remove();
           if(!visited[curr]) {
               System.out.println(curr);
               visited[curr] = true;
               for (int i = 0; i < list[curr].size(); i++) {
                   Edge e = list[curr].get(i);
                   q.add(e.dest);
               }
           }
       }
    }

    //Finding all possible paths from one point to another point

    public static void ALlpaths(ArrayList<Edge> list[],boolean[] visited,int src,int d,String path){
        if(src==d){
            System.out.println(path);
            return;
        }

            for (int i = 0; i < list[src].size(); i++) {
                Edge e = list[src].get(i);
                if (!visited[e.dest]) {
                    visited[e.dest] = true;
                    ALlpaths(list, visited, e.dest, d, path + e.dest);
                    visited[e.dest] = false;
                }
            }

    }

    public static void main(String[] args) {
      int V =7;
      ArrayList<Edge> list [] = new ArrayList[V];
      creategraph(list);
      boolean b [] = new boolean[V];
      int src =0;
      b[src]=true;
//      dfs(list,b,0);
        ALlpaths(list,b,src,5,""+src);
    }
}