bfs solutions java

                                    #include<iostream>
#include <list>
 
using namespace std;
 


class Graph
{
    int V;   
 
  
    list<int> *adj;   
public:
    Graph(int V);  
 
    
    void addEdge(int v, int w); 
 
    
    void BFS(int s);  
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); 
}
 
void Graph::BFS(int s)
{
  
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
 
   
    list<int> queue;
 
   
    visited[s] = true;
    queue.push_back(s);
 
   
    list<int>::iterator i;
 
    while(!queue.empty())
    {
       
        s = queue.front();
        cout << s << " ";
        queue.pop_front();
 
      
        for (i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}
 

int main()
{
    
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 
    cout << "Following is Breadth First Traversal "
         << "(starting from vertex 2) \n";
    g.BFS(2);
 
    return 0;
}

                                    package com.javaaid.hackerrank.solutions.tutorials.ctci;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

class Graph {

  private final int V;
  private int E;
  private ArrayList<Integer>[] adj;

  Graph(int V) {
    adj = (ArrayList<Integer>[]) new ArrayList[V + 1];
    this.V = V;
    this.E = 0;
    for (int v = 1; v <= V; v++) adj[v] = new ArrayList<Integer>(V);
  }

  Graph(Scanner in) {
    this(in.nextInt());
    int E = in.nextInt();
    for (int i = 0; i < E; i++) {
      int v = in.nextInt();
      int w = in.nextInt();
      addEdge(v, w);
    }
  }

  public int V() {
    return V;
  }

  public int E() {
    return E;
  }

  public void addEdge(int v, int w) {
    adj[v].add(w);
    adj[w].add(v);
    E++;
  }

  public Iterable<Integer> adj(int v) {
    return adj[v];
  }
}

class BreadthFirstPaths {

  private int s;
  private boolean marked[];
  private int edgeTo[];

  BreadthFirstPaths(Graph G, int s) {
    marked = new boolean[G.V() + 1];
    this.s = s;
    edgeTo = new int[G.V() + 1];
    bfs(G, s);
  }

  private void bfs(Graph G, int s) {
    Queue<Integer> q = (Queue<Integer>) new LinkedList<Integer>();
    q.add(s);
    while (!q.isEmpty()) {
      int v = q.poll();
      marked[v] = true;
      for (int w : G.adj(v)) {
        if (!marked[w]) {
          marked[w] = true;
          edgeTo[w] = v;
          q.add(w);
        }
      }
    }
  }

  public Iterable<Integer> pathTo(int v) {
    if (!hasPathTo(v)) return null;
    Stack<Integer> path = new Stack<Integer>();
    for (int x = v; x != s; x = edgeTo[x]) path.push(x);
    path.push(s);
    return path;
  }

  public boolean hasPathTo(int v) {
    return marked[v];
  }
}

public class BFSShortestReachInAGraph {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int q = sc.nextInt();
    for (int i = 0; i < q; i++) {
      Graph G = new Graph(sc);
      int s = sc.nextInt();
      BreadthFirstPaths bfp = new BreadthFirstPaths(G, s);
      for (int v = 1; v <= G.V(); v++) {
        if (s != v) {
          if (bfp.hasPathTo(v)) {
            Stack<Integer> st = (Stack<Integer>) bfp.pathTo(v);
            int sum = 0;
            for (int x = 1; x < st.size(); x++) {
              sum += 6;
            }
            System.out.print(sum + " ");
          } else {
            System.out.print(-1 + " ");
          }
        }
      }
      System.out.println();
      sc.close();
    }
  }
}