bfs solutions java

1# tree level-by-level traversal. O(n) time/space
2def breadthFirstSearch(root):
3    q = [root]
4
5    while q:
6        current = q.pop(0)
7        print(current)
8        if current.left is not None: q.append(current.left)
9        if current.right is not None: q.append(current.right)

1package com.javaaid.hackerrank.solutions.tutorials.ctci;
2
3import java.util.ArrayList;
4import java.util.LinkedList;
5import java.util.Queue;
6import java.util.Scanner;
7import java.util.Stack;
8
9class Graph {
10
11  private final int V;
12  private int E;
13  private ArrayList<Integer>[] adj;
14
15  Graph(int V) {
16    adj = (ArrayList<Integer>[]) new ArrayList[V + 1];
17    this.V = V;
18    this.E = 0;
19    for (int v = 1; v <= V; v++) adj[v] = new ArrayList<Integer>(V);
20  }
21
22  Graph(Scanner in) {
23    this(in.nextInt());
24    int E = in.nextInt();
25    for (int i = 0; i < E; i++) {
26      int v = in.nextInt();
27      int w = in.nextInt();
28      addEdge(v, w);
29    }
30  }
31
32  public int V() {
33    return V;
34  }
35
36  public int E() {
37    return E;
38  }
39
40  public void addEdge(int v, int w) {
41    adj[v].add(w);
42    adj[w].add(v);
43    E++;
44  }
45
46  public Iterable<Integer> adj(int v) {
47    return adj[v];
48  }
49}
50
51class BreadthFirstPaths {
52
53  private int s;
54  private boolean marked[];
55  private int edgeTo[];
56
57  BreadthFirstPaths(Graph G, int s) {
58    marked = new boolean[G.V() + 1];
59    this.s = s;
60    edgeTo = new int[G.V() + 1];
61    bfs(G, s);
62  }
63
64  private void bfs(Graph G, int s) {
65    Queue<Integer> q = (Queue<Integer>) new LinkedList<Integer>();
66    q.add(s);
67    while (!q.isEmpty()) {
68      int v = q.poll();
69      marked[v] = true;
70      for (int w : G.adj(v)) {
71        if (!marked[w]) {
72          marked[w] = true;
73          edgeTo[w] = v;
74          q.add(w);
75        }
76      }
77    }
78  }
79
80  public Iterable<Integer> pathTo(int v) {
81    if (!hasPathTo(v)) return null;
82    Stack<Integer> path = new Stack<Integer>();
83    for (int x = v; x != s; x = edgeTo[x]) path.push(x);
84    path.push(s);
85    return path;
86  }
87
88  public boolean hasPathTo(int v) {
89    return marked[v];
90  }
91}
92
93public class BFSShortestReachInAGraph {
94
95  public static void main(String[] args) {
96    Scanner sc = new Scanner(System.in);
97    int q = sc.nextInt();
98    for (int i = 0; i < q; i++) {
99      Graph G = new Graph(sc);
100      int s = sc.nextInt();
101      BreadthFirstPaths bfp = new BreadthFirstPaths(G, s);
102      for (int v = 1; v <= G.V(); v++) {
103        if (s != v) {
104          if (bfp.hasPathTo(v)) {
105            Stack<Integer> st = (Stack<Integer>) bfp.pathTo(v);
106            int sum = 0;
107            for (int x = 1; x < st.size(); x++) {
108              sum += 6;
109            }
110            System.out.print(sum + " ");
111          } else {
112            System.out.print(-1 + " ");
113          }
114        }
115      }
116      System.out.println();
117      sc.close();
118    }
119  }
120}
121

1#include<iostream>
2#include <list>
3 
4using namespace std;
5 
6
7
8class Graph
9{
10    int V;   
11 
12  
13    list<int> *adj;   
14public:
15    Graph(int V);  
16 
17    
18    void addEdge(int v, int w); 
19 
20    
21    void BFS(int s);  
22};
23 
24Graph::Graph(int V)
25{
26    this->V = V;
27    adj = new list<int>[V];
28}
29 
30void Graph::addEdge(int v, int w)
31{
32    adj[v].push_back(w); 
33}
34 
35void Graph::BFS(int s)
36{
37  
38    bool *visited = new bool[V];
39    for(int i = 0; i < V; i++)
40        visited[i] = false;
41 
42   
43    list<int> queue;
44 
45   
46    visited[s] = true;
47    queue.push_back(s);
48 
49   
50    list<int>::iterator i;
51 
52    while(!queue.empty())
53    {
54       
55        s = queue.front();
56        cout << s << " ";
57        queue.pop_front();
58 
59      
60        for (i = adj[s].begin(); i != adj[s].end(); ++i)
61        {
62            if (!visited[*i])
63            {
64                visited[*i] = true;
65                queue.push_back(*i);
66            }
67        }
68    }
69}
70 
71
72int main()
73{
74    
75    Graph g(4);
76    g.addEdge(0, 1);
77    g.addEdge(0, 2);
78    g.addEdge(1, 2);
79    g.addEdge(2, 0);
80    g.addEdge(2, 3);
81    g.addEdge(3, 3);
82 
83    cout << "Following is Breadth First Traversal "
84         << "(starting from vertex 2) \n";
85    g.BFS(2);
86 
87    return 0;
88}