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}